Paper maps before that. If you were in AAA you could get a "trip map" that was a complete route with turn by turn directions and a spiral bound, printed map that you paged through as you traveled, but paper maps worked well. Not as convenient as a phone but not terrible either.

The AAA maps are pretty great. I keep one of their spiral bound maps of my region in my trunk just in case.