Spotify is a free, legal, ad-supported way to stream music. Their catalogue of music is HUGE and whilst there is no native-linux client there are very comprehensive instructions for how to run it under wine on their own site (this is very easy too, no hacking around).
At the moment, the service is in beta and you need to be invited to join it, or pay for one of the premium services. However, for a limited time, if you’re in the UK you can use this link to sign up: tinyurl.com/spotifylink. There are native clients for Windows and Mac OSX… perhaps with a little bit of lobbying a native Linux client will be released too.