Whatever you decide, you should get from the BLM (or order from any specialty map store) a land-ownership map of whichever state you are going to hunt. It will show ownership by color - usually blue for state land, green for national forest/grassland, yellow for BLM, white for private, etc. Makes it quite easy to plan your coyote massacre itinerary!
Also, be aware of each state's regulations for the use of state land. In Colorado, all state land is controlled by whichever rancher leases it from the state - you still have to get permission to use it from the lessee. In other states, who knows. There are also things like state trust lands, which are open to the public for hunting during specific months. And, of course, make sure the yote season is open! Usually it is year round, but we had one year here in CO ('96/'97 winter) that we actually had a closed season (fall-winter only) on yotes. Fortunately that didn't last.
Good advice in other posts above. Wyoming has tons of public lands (mostly plains and desert), used to not require a license for out-of-staters to hunt yotes, and has very few people. Utah has some fascinating and stunning scenery. Colorado has lots of interesting and varied public lands, mostly on the west slope along the Utah border.
Pick a couple states (not too many - they're REALLY HUGE out here!), get those maps, and start planning!