We had several atlas books of regions and neighborhoods. Looking up an address was an exercise in getting the right book for the neighborhood, then using an index which noted which block of the map that house number was in (eg 'c10' using a grid with numbers across the top and letters down the side).
Plotting a course from where you were to this location was also exciting and required patching together multiple maps.
Actually following that course in real life was another challenge altogether and really required visualizing what you saw on the map since, as noted, there aren't many street names.
I'm honestly surprised we were able to succeed at getting to places as often as we did.
I kind of miss that experience, just plugging an address into a phone and following directions is much less exciting.