I've been using Pandora for years, really love that service. It really does a good job in keying in on the type of stuff you enjoy. The up and down voting is really the most important part of the whole system. I have a station that is roughly 2 years old now, I can leave that thing on 24 hours a day and never hear a song that I dislike.
I'm a little bit of an addict when it comes to music though. Finally had to get a ZuneHD last year to try and curb my spending habits when it came to buying music. Love that Zune Pass.
I also use
GrooveShark when I'm on the laptop or a friends computer and just want to listen to some quick music, since it lets you pick the exact songs you want to play.
I like the website
TheSixtyOne, when I want to hear some indie bands I've never heard of before. The site has a beautiful user interface.
Last.fm is pretty cool too, though I don't really use it for the radio, rather just to track my listening habits when I play my music on iTunes and "scrobble" music from my iPhone / iPod. I also like how they compare your listening habits with other users and give you a little "your music compatibility with XXX is 'Super'", etc. I've met some cool people on there simply because we loved all the same music.