It's died down a bit, but for a while in the late-90s / early-2000s, there was a whole research subfield dedicated to retrieving audio via humming, which has some interesting stuff in it: http://scholar.google.com/scholar?hl=en&q=%22query+by+hu... It's got a nice mixture of signal processing, sequence alignment, and approximate pattern matching problems all rolled together.

I'm fairly sure that SoundHound does not match hummed or sung queries with album recordings, but with other hummed melodies submitted by users and labeled with the song ID.

I would imagine the algorithm is different, since the Shazam algorithm is designed to find exact matches corrupted by noise, EQ, etc., and two hummed versions of the same melody may vary in key, tempo, and timbre, and have small rhythmic differences.