Pandora is an online custom radio station which streams music to you based on what you tell it you like/don’t like. Alex tipped me off about this a few weeks ago as its been keeping him alive at his job. What makes Pandora worth your time is that its well designed, usable and attractive interface and it will actually find music that you like, and didn’t know you liked!
For example, I entered “Barenaked Ladies” as the starting artist for a new station and I’ve enjoyed Teddy Boy by Paul McCartney and Fly From Heaven by Toad the Wet Sprocket. I’ve got another station going based of Kosheen and I’ll probably start one from Blink 182 and Laid by Matt Nathanson. Yep, you can start them based of individual songs as well as artists.
You used to get 10 hours free then had to subscribe (worth it), however they have just announced a long term, ad-supported free version. There are no ad’s up yet (but they will come), and you can still pay if you wish for ad-free (cheap).
Pandora’s Blog lists some of the version 2 changes here. They look like this already good product is getting even more promising!
EDIT: Please know that Pandora is riegned in by the licences it has for its music. For example, you can only skip so many tracks per hour, you can’t type a specific song name into a station and expect it to be played straight away, but it will play eventually (i.e. no specific requests)