Basic IR intro, skip this paragraph if you know the drill: Basic text search can be thought of as "looking for your search terms in relevant documents" (ala TF-IDF[1]). More sophisticated search layers on various other metrics. Google famously employed its Page Rank algorithm[2] as one such example. Modern search engines with enough traffic can also use click streams themselves as a search metric: for the given search terms, which link(s) were actually clicked on?
Back on point: What users click on and where they go (if the data is available) and how many times they go (again, if the data is available) are usable metrics, physical equivalents of click-stream traffic.
Likewise, information from other sources about relatedness of locations can also be integrated. Think "semantic fisheye views." E.g. you clicked on a pub, and Google knows about other pubs and bars in the area. Or perhaps you clicked on a Yoga studio, which causes different location relationships to be (de-)emphasized. Google at very least can draw on their classic search data as well as the more structured location and business data they've been building for some time.
It's like the way pagerank works. It doesn't rely on explicit rankings, it relies on extracting implicit trust and authority information from the natural and organic ways that people link things on the web.
You think when Google Maps was launched their primary competitors (e.g. MapQuest) had anything comparable? Maps was one of the first, large scale, Web 2.0/AJAX applications. At the time, most other mapping products were still reloading an iframe or the whole page everytime you needed to change the map.
Gmail was lightyears better in both performance, spam filtering, organization, and speed compared to other major WebMails at the time.
The New Google Maps is a quantum leap over competitors like Bing Maps, even native iOS maps.