While Pandora may be old news to most of you, I just tried it for the first time yesterday, admittedly because both of my favourite streams were down and my Youtube playlist was getting old. I was amazed by what I saw, and am now a convert.
Pandora is an extension of the Music Genome Project, a grand effort to basically classify everything in the world of music. This leads to a gargantuan collection of data that can be mined. Not only do they have the official discography and history of the band, but also the 'genome' of the band. For example, a particular band may have flags for "hard rock roots", "electric guitar solos", and "vocal harmonies".
Pandora basically builds a radio on top of this information. All you do is type in the name of a band or song that you like. It uses its knowledge to find other songs it thinks you'll like. Then, using a simple flash player, it plays a continuous stream of similar songs for you! I tried this a couple of times, naming a band I liked each time. The result was astounding - out of the next 20 songs, I'd say about half are among my current favourite songs, and the other half were songs I hadn't heard but loved.
You can apply feedback to the process too - a simple "thumbs up" or "thumbs down" balances the station closer or farther from attributes similar to the song you're listening to (to the point where entire bands can get 'banned' from your station). You can also add more seed bands to your station to vary certain attributes (but reinforce commonalities). For any song that plays, Pandora can tell you exactly why it chose the song for you.
How is this all legal? Well they pay the major studios, just like a radio station does. Anytime you click on the webpage (to thumbs up, pause, etc), they adjust the background of the page to an advertisment. Alternatively, you pay a small fee for a premium service with no ads. Also, of course, every band and song has a link to Amazon/iTunes, and you know that they're getting a cut of that.
However, since they want to be considered a radio station, they have to make some concessions. You can pause, but not rewind. You can't request specific songs. You can't save the song to your computer to play later.
Also, unfortunately, it's US-only for now, though several have found ways to circumvent this check.
Still, if you have access, give it a try. If you're on Facebook, my profile lists my stations if you're curious.