I answered this exact question a while ago when content identification on SoundCloud was being discussed. Companies like Audible Magic have been working with labels for a long time, building substantial databases of audio tracks. Software scans files, produces fingerprints which are... Well, I'm not privy to the exact spec, however logically it's a combination of duration, detected pitch, harmonic and spectral content, patterns within the spectral content (drums and basslines are very characteristic, and when you use samples those patterns will be identical for every repeat) plus other various factors of the waveform. The way the fingerprint is generated makes the detection process resilient; a guy did some unscientific testing a while ago when YouTube introduced their Content ID system (utilising Audible Magic's backend systems) where he manipulated, reversed, pitched up/down and sped up/down a known file and then noted down how extremely the waveform had to be manipulated in order for it to be unrecognisable. (in short: a LOT).
This is also how Apple's iTunes Match service will be identifying catalogue; the fingerprint detection software is integrated into the forthcoming version of iTunes (so it will scan your files locally then just upload the resulting fingerprints for comparison on the server).