I bought some natural cypress mulch for my tomatoes and then I was told not to use it because it would steal nitrogen.
What is the best mulch and is there one that you can till in after the garden is gone?
You were told something only partially correct. At the mulch/soil interface, bacteria will use nitrogen from the soil to break down the mulch. This won't affect the roots of your tomatoes - they're deeper than the bacteria in the soil. And when the bacteria die, they release the nitrogen they've "stolen" anyway. Their life cycle is short. Don't worry about this and just use the cypress.
Personally, I use cocoa bean hulls for mulch in my vegetable garden because they break down over the course of the season. I've never noticed a problem with yields when I compare to the years when I used no mulch.