In addition to Pandora, another website I’ve come across recently and really enjoy is PureVolume.com.
There are a couple of reasons I like it. For one, unlike Napster or some of the other music services, you can actually listen to more than 30 seconds of a song before deciding whether you like it or not. Most artists on PureVolume have three or four songs that you can listen to in full before you do something silly like go out and purchase their music. Some artists even have free MP3 downloads, which is awesome. I get to build my MP3 library for free without using a dubious file sharing program. (For the record, I purchase all my music using either Napster or MSN Music.)
Anyway, there are a ton of artists you might not find otherwise. My personal favorite discovery is Coheed and Cambria.
For the record, MySpace has a lot of artists profiles and also offers full-length songs and the occasional free download. The site is more geared towards social networking, however.