Before MapQuest, you'd carry around a six county atlas, and a state map. If you had to go somewhere outside the metro area, you'd use the state map to get to the city, then stop at the first gas station you saw there to look at their map on the wall, or ask to look at their phone book for the map in there.
We had those big red atlases (Atli?) with the glossy covers from over half the US states, and smaller maps for all the counties in Virginia, NC, SC, and about half of TN. Huge ass stack of em in both door panels, under each seat, and several on the back seat. My brother collected them whenever he could. I think he's still depressed he never finished his collection before giving up and finally getting a gps (only like 2 years before decent smart phone gps)