If I didn't have a warmshowers host(check out couchsurfing too!), I'd roll into town and hit the library first. You can usually find out everything you need to know there. I simply could not afford to pay for a place to flop every night--nor did I want to. I camped under a cell tower in Maine, behind a utility shed in Kansas, in the woods in NY, CO, NM and elsewhere. The thrill and challenge of finding a place to camp provided a real spice to the journey--and often the best camping. I HATE KOA's with a special passion. Besides being very expensive (about $25/night out west), they are freakin' noisy so close to freeways and such. The only good one I've stayed in was in Mt. Shasta, CA.--very nice with great views of the mountain.
Be flexible and creative. It's all part of the adventure.