If you're downloading copyrighted material, (like mp3's of hit songs or modern content) without paying for it, chances are, it's not legal. Very few artists choose to allow their music to be shared freely. Most of the apps that advertise free mp3 downloads are really just search engines that search the web for links to the mp3's and point you to them, which makes them just a search engine, falling into a legal loophole since they're not actually hosting or sharing the files themselves. It's like the torrent websites, they're not actually hosting anything, they're providing a search engine that can be used to find copyrighted material. Really, you could probably find the same content with Google if you put your mind to it. Now don't get me wrong, there are some legal free music services (Pandora, for example) but those usually have some sort of limitation. There are also services that will charge you a Monthly fee and allow you to download music (Rhapsody) or some that allow you to purchase music by the song (Amazon). All of those are still getting royalties back to the artists and recording companies. I'm not aware of any free music service that allows unlimited legal music downloads, presumably something could exist on an ad supported model, but if it does, I'm not aware of it. Most likely the apps that you see promising free mp3 downloads, while they may not be breaking the law themselves, are not offering you legal downloads.
I've downloaded 643 mp3 songs off of a site called Easy MP3 Downloads. Every one of them have good sound quality. If I'm not able to find a particular song that I want there, which is rare, I try a site named 4Shared. Both are in the Market. Good luck.