How do services like Google Latitude geolocate my laptop perfectly with no GPS?

Google Latitude uses a proprietary Google service that operates on the exact same principal as the more popular Skyhook Wireless system. The software takes readings from your wifi adapter, and compares these to a database of known wireless networks and their locations, allowing for the triangulation of your position based on signal strengths. This allows the service to determine an accurate location without GPS.

The database of WiFi networks is quite extensive and comes from multiple sources. First, they likely import from public databases like WiGLE. Second, whenever a laptop running the service sees a new network, it's reported to the service. When multiple computers report a new network, its position can be triangulated based on the position of the known computers. It is fairly simple to keep a database of all wireless networks because all wireless networks (even those with the same ESSID) have a unique interface MAC address assigned by the manufacturer.

[Please upvote/accept @jcrawfordor's answer, but I wanted to add some information and the comment box character limit was too small, so I decided put this as an Answer instead.]

Please note the web browser Geolocation API. You probably forgot that the first time you visited Google Latitude, you gave your browser permission to let Google Latitude access your Mac's Location Services data. For browsers that don't support the Geolocation API natively, there are downloadable browser plug-ins or Java applets that provide this kind of feature, almost always by querying your Wi-Fi card for what networks it can see around it. Skyhook's "Loki" technology is a Java applet, but since it needs to access system APIs to query your Wi-Fi card for network scan data, your browser has to ask permission before it will run Loki. Usually Java apps are completely sandboxed and don't require permission to run because they can't violate your privacy or access anything on your system.

Here's what Safari does when you first visit Google Latitude:
.

Here's what Safari does when you try to load Skyhook's Loki applet: