I lived in Tokyo before Google Maps, and the answer was: printed maps. Every business card had a map on the back, every ad for an event had a map, every personal invitation had a hand-drawn map. But yeah, if you were going somewhere as a group, you'd meet at a known point (outside train station etc) and then head over together.

If you were roughing it on your own and only had the address, things got more interesting. Train stations always had detailed maps of major landmarks, so finding those was not an issue. If you were looking for something too small to be covered (say, a restaurant), you'd head to the chōme and then start winnowing down. Police boxes (koban) always had detailed neighborhood maps bolted to a wall nearby listing every single business and family by name, albeit usually in handwritten Japanese only, and you could ask the cops for directions too.

The final boss was the non-linear numbering house scheme though. Some friends and I once spent a fruitless hour searching for the HR Giger bar in Tokyo, which we knew was at X-Y-Z, but only managed to find X-Y-(Z+1) and X-Y-(Z-1).