If Google was smart they would have collected cell tower and WiFi data along with the Google Maps Street View images. They've already canvased most of the major cities in the U.S. once.
Google can use any number of methods to determine the location. If the device has a GPS receiver they'll obviously use that, otherwise they'll fall back to cell tower and WiFi data, like the iPhone does.
GPS can be accurate to a few meters, WiFi to a few hundred meters, and cell tower quite a bit less accurate. In practice the iPhone's location feature very well in populated areas.
Desktop computers can even use IP addresses as a very rough estimate (maybe down to the city or county).
