I have an app and would like to know if there is any kind of API for a service similar to Shazam where I can hold my phone up to a music source and be told of the song guess? It could work well with my app, but I can't find anything about Shazam API and I don't know any other service that does what I want (but am open to anything)
Audio recognition services are provided by a number of companies, many of which license these services for a fee. None are cheap, requiring significant repositories of signatures / music catalogs and computational capacity. Check out the folks who own the technology used by Shazam - Landmark Digital Services, the makers of Soundhound - Midomi, or Gracenote's MusicID. There are others, but these are probably three of the biggest players currently.
UPDATE (11/8/12): To note, Shazam apparently has reacquired the rights to the recognition technology and Landmark Digital is now defunct. Also, as noted in another answer, Echonest now provides a recognition technology, Echoprint, that for some uses appears to be free.