How does iTunes Match match the songs in your library?
I already answered a related question. I may not know the most definite answer, But I read that iTunes Match uses Gracenote's MusicID program. It seems MusicID uses the following techniques to identify songs.

MusicID-featured Identification Technologies:

CD Identification: Using the CD’s unique Table of Content (TOC), MusicID can identify CDs released around the world. Even with multiple pressings and release dates, patented fuzzy matching enables accurate recognition.

Stream Identification: Using an audio waveform fingerprint technology, MusicID can identify music with short audio samples anywhere in the song.

Digital File Identification: MusicID can identify individual songs or albums in a user’s collection regardless of source, format, or tag information. Utilizing a multi-step process which combines stream identification with textual information analysis from the file’s embedded tags, file name, directory path, and other related files in the user’s collection, individual or groups of songs can be matched to albums.

More here. 

To answer your question, they perform some fuzzy text matching algorithm to map meta data and also perform audio waveform analysis.