Well here is an easy way to know if it's illegal. If you want to download songs you can find on a CD at the store, it's illegal. If you want to download songs from someone that's not selling CD's at a store, or is not signed to a label, and/or with the band's permission, it's legal. If you want to buy some songs, here are some sites.

Amazon
Napster
iTunes

Amazon sells digital downloads now.