You chunk a song into small segments and create a sort of "fingerprint" for each piece using Fourier analysis or similar. (So a song segment is represented by a frequency histogram, similar to this: http://www.flickr.com/photos/svartling/4229109164/ ) The fingerprints are stored in a DB.
To match a song fragment, chunk and analyze it in the same way. For each segment, find the closest match in the database. If most of the closest matches belong to the same song, and appear in the same order as in the song fragment you are trying to find, you have a match.
Creating fingerprints from a series of video segments is roughly similar, Fourier can be used for 2D images as well.
Doing it like this, you can reduce the volume of data you need to compare against with several orders of magnitude. Scaling to YouTube volumes is still hard, but that's the sort of scaling a company like Google already has plenty of experience in.