This scientific paper (though short on sources), explains how Shazam, the audio recognition service, works.
