Spotify is awesome, i'm too lazy to explain it myself so i'll just post a link: Spotify, An Alternative to Music Piracy | TorrentFreak
I've been using GrooveShark for a while and I really like it. It's like Pandora minus the randomness (that I hate) and you can set up a queue as well as have it 'recommend' songs that you'd like (ala Pandora). And surprisingly, the audio quality of the songs on Grooveshark is very good (to my astonishment - and you can flag the bad audio as well). Spotify doesn't work here in the US though.
Yeah it doesn't work yet in a lot of countries, but you can make an account anyway: Digg - Spotify, An Alternative to Music Piracy
