The best way to use an application that identifies songs that it hears, like Tunatic, is to always have it with you in your cellphone.
AT&T Wireless is offering exactly that in the US (this type of service has already been available in Britain).
It's very simple: when you hear a song and you don't know who it's by just dial #43 (#ID) on your cellphone, hold the phone near the speaker for 15 seconds, and they'll send you an SMS with the name of the artist and the name of the song.
For now it's free but later on they'll start charging $0.99 for each time you use the service.