It uses acoustic fingerprinting. I believe the songs are analyzed on the client side, and the fingerprints are sent to Apple. Same as iTunes genius and apps like Shazam.
http://en.wikipedia.org/wiki/Acoustic_fingerprint

Re: Google Music
There are some that like "free". There are others that are willing to pay to have integration and good design. Examples I'm familiar with are home automation tinkerers like X10/zigbee/Zwave, others like Bang & Olufsen who have done it for years, works pretty well, but charges a lot.

I prefer the system that integrates with our existing 4 iPhones, 11 Macs, and 6 Apple TVs.