> so the questions begins... shouldn't there be a better way to
determine 
> land ownership? is there a good website or some sort of free map 
> available?  can a Trust Land Permit be obtained over the phone or
internet?

Someone's already pointed out how to get the permit, but this site has
all the details:
http://www.land.state.az.us/programs/natural/rec_offroad_permit.htm

The State Land Department (AKA "The Land Trust") has no objection to
Geocaching. But caching or otherwise, you can be nicked for a pretty
hefty fine if you are found on Trust Land without the permit, so it's a
pretty good investment of fifteen or twenty dollars. For most folks
that's probably less than the gas it costs to drive to a patch of Trust
Land these days.
Steve
Team Tierra Buena