They "fingerprint" the audio and then compare the fingerprint to a large corpus. The hard part is fingerprinting that is resilient to noise (and position within a track!) and a fast way to search the corpus of known fingerprints.