I remember arriving in China in 1985 and noticing that there were no commonly used phone books, either white or yellow pages. It was hard to find phone numbers, let alone addresses. To find a new place you basically went to the general vicinity and asked the locals. Now, with addresses and phone numbers changing so often due to urban construction, many locations in a print phone book would be quickly out-of-date anyway.
Location finding has got to be as indispensable an online service for Chinese people as it is for Americans (what would we do without Mapquest?). MaryAnn O’Donnell recently pointed out the Xuntu digital map site, which provides a surprisingly broad range of Beijing “maps.” Most are addresses and descriptions rather than actual cartography–but still quite useful.