I don’t know the details, but it can listen to any portion of a song for ten seconds or so, then identify it from its database. I assume Apple is using something similar, in that it can “play” a sample of the uploaded file and match the characteristics using an algorithm like Shazam’s to ID the track.