How does iTunes Match match the songs in your library? There seems to be a lot of information about iTunes Match, but I couldn't find any that describes exactly how the algorithm works. Is it something as simple as comparing song names/artists, or is some kind of checksum done? 

I'm asking since I've got some music which isn't even properly tagged (titles/artists mismatched) and since iTunes Match is not yet available in Poland I can't really test how it would be behave with such files. So is it something really complicated and nicely done which involves music analysis or something as trivial as checking song names? Does anyone have detailed information on it?
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.