There are tons of legal MP3 sites out there that allow downloading, some free, some for sale. The most obvious would be
MP3.com.
A few more that came up
Googling for legal+mp3 are:
http://www.onlinetonight.net/mp3/
http://www.narcopop.com/musicians/
http://mp3.dubroom.org/
Search engines are a web user's best friend...