It isn't legal if the music is copyrighted and they don't have the rights to stream it, and chances are they don't. Just because it's illegal doesn't mean it people don't do it though.
Myspace was sued by Universal Music for unauthorized sharing of music and music videos. Just this April they settled, with Myspace paying $$$$$$$ and the a joint venture created - the newly launched Myspace Music. Myspace could work a deal like that because they are such a huge player, but even so it took almost 2 years of litigation. More info: http://www.nytimes.com/2006/11/18/technology/18myspace.html http://www.alleyinsider.com/2008/4/myspace_settles_with_universal_music_launching_myspace_music_nws_