Wow, what a crazy thread here....
It is very simple to collect anywhere in the US. There are a few things to do and they are all free and very easy to do.
Federal Land..... go to the Forestry dept near the area you want to collect. Ask them for a CONDITIONAL USE PERMIT. They are free and you can collect trees with them. Every national forest has them. You can get them to collect rocks, trees, basically anything in the forest. There are guidelines with these but for the most part it will get you what you need.
State land...... BLM, same thing, they offer permits to collect trees. You might have to sit with the land use director like I have in the past and talk with him a bit. But that was because I told him I was looking for small stunted, twisty, Dr. Seuss trees. He wanted to make sure I stayed out of the protected areas. Again, free permit to collect trees on state land.
Private land, super easy......knock on the door and be a likable person. Let them know that you are looking for a certain type of tree for your landscape or around your pond. If you get a good vibe then let them know you will be using it for bonsai. But the only thing they can do is say no. Big deal. Most times they say yes. But it is all in how you come across, if they think you are a shy creepy guy then you will get a big NO very quick.
That covers all land. Really getting the nod to collect is easy.....finding a tree worthy of collection is the hard part.
Letters won't work, they won't take the time to read it and will throw it away after the first sentence. Be personable and upfront.
Happy collecting.....