Read Thread: Just Starting
I recommend finding several letterboxes before planting. That way you'll see what places people like to letterbox and what places people avoid (schoolgrounds, playgrounds, prisons, poison ivy patches, landfills, Walmart dumpsters)
The Code of Conduct has some information.
Find your state board and see if there's anybody in your area.
By no means a complete list, check the Land Manager Policies section of the help pages. It'll at least give you some information. You can also try googling phrases like "letterboxing in texas state parks" or whatever is relevant to you or the specific website with information about a park you're interested in. Most of them don't typically have information about letterboxing, but if there's a section on geocaching, you'll probably be safe assuming the rules will be similar to letterboxing.
What do you mean to avoid ivy patches? My first plant was in an ivy patch!
Seriously, I didn't know what poison ivy looked like, and I ended up planting in a sparse patch of poison ivy. In my defense, even if I'd know what do look for it was early in the year, before it really got growing. I did end up moving it out of that patch, closer to the trail.