How does the technology behind iTunes Match work?
In late 2009, Apple bought LaLa.com, a site that did pretty much what present day iTunes Match does.

It analyzed tracks you already owned, and allowed you to stream the ones you already had on your hard drive.

The way the technology works is by analyzing the waveform of the music file and matching it to an existing database of known song digital audio fingerprints. 

Obviously, that's way oversimplifying, but the basic idea of why you don't have to upload a lot of your library, as iTunes Match and formerly LaLa.com have an existing db of song "fingerprints."