They know that when certain location data sources provided chertain signals, the user in question checked in at a location with a known map position and known constraints to the location.
There aren't many sources of location data with that extra information.
More advanced techniques relying on radio signal strengths, RTT time, and other observables [2] are being developed but I don't know of any in widespread use. I wouldn't be surprised to see something emerge soon though.
[1] http://en.wikipedia.org/wiki/Assisted_GPS
[2] One example: http://ws2.binghamton.edu/fowler/Improving%20WLAN-Based%20In...
Now whether Android actually uses the wifi data to determine location, as opposed to simply collecting it and manually disabling course-location if you don't send them wifi data, I have no idea. It does seem to be related though to the new Geofencing API available in the latest versions of Android.
EDIT: Sources!
http://www.zdnet.com/blog/networking/how-google-and-everyone...
http://developer.android.com/training/location/geofencing.ht...
This can be observed in practice as Android tablets and Apple devices with no GPS or cell radio at all can still locate themselves relatively well.
http://www.skyhookwireless.com/apps-enterprise/ has the marketing-bling diagram of Skyhook's use of multiple observables to determine location; even as of 4 or so years ago when I last used their API you sent them MAC + RSS and got back location.
http://en.wikipedia.org/wiki/Wi-Fi_positioning_system
"Commercial providers of this type of positioning service include Google,[1] Navizon, AlterGeo[2] and Skyhook Wireless."
If not, why does my Android phone ask me to turn on wi-fi to enhance location information?
Edit: To answer my own question, the Android source code for this used to be available. At the time, they passed the visible wi-fi SSIDs and the cell-tower IDs, but not the signal strength (they had it in both cases). Not sure why they didn't pass the strength. Maybe it made caching really hard; maybe it sufficed just to pass them in order; maybe it didn't make a big enough difference... http://www.netmite.com/android/mydroid/frameworks/base/locat...
To me, this actually raises more questions. It's so surprising to me that Google don't pass the signal strengths ("everyone knows" that is how triangulation works), that I'm thinking the real secret is that the signal strength isn't actually helpful. In other words, I'd bet Google tried what FourSquare have discovered, and rejected it. Or it's patented :-)