I've been flirting with music streaming systems for a while now, most notably Pandora, but none have really been what I'm looking for. Pandora runs in your web browser and attempts to create a radio station of music that is similar to a song or artist that you like. It's an interesting project, but lacks the control I would prefer - I sometimes want to listen to particular tracks, not a random selection of similar tunes. The nail in the coffin with Pandora for me though, is that it isn't available outside the US any more. I can use a US based proxy server to get around the restriction, but that's another barrier to entry.
I was recently introduced to Spotify, a free, legal music streaming system. You simply register at the website, download and install the application, then you can search for and listen to pretty much anything you like. It's incredibly responsive, finding tracks very quickly and seems to have nearly everything I've tried searching for (apart from the bands that don't appear anywhere else - The Beatles, etc). The user interface is minimal and simple to use too. I've been using it for a few days now and haven't noticed any dropped connections whilst streaming music.
On the downside, sound quality is average, though it's good enough for the light headphones I use in work. Also you have to listen to a short audio advert every few tracks (one every half an hour or so I reckon), with an option to pay a subscription (GBP 9.99 per month) if you don't want this. The ads are distracting if you're trying to listen to an album in full, but it's a price I'm willing to pay given the value of the service.
Overall, this is a great service. I hope their business model is profitable enough to survive.