Over the past few days, I've been having a lot of fun with with an online music service called Grooveshark. Found out about it from Dedoimedo; check out his article: http://www.dedoimedo.com/computers/grooveshark.html
I haven't created an account there (yet), but each morning I've been going there, searching for songs, and dragging and dropping them onto the playlist at the bottom of the window. The service works from inside a tab in Chromium, as shown in the screen shot below (running it in Fedora 14). The interface is friendly, and I can usually find whatever song that comes to mind.
There are ads along the right side, but almost all of them are blocked in Chromium by Adblock. Flashblock has to be disabled for the site, though. The settings include modes like "shuffle" and "loop," stuff you'd expect in any good music player.