Similar to above, I use spotify and it's pretty simple to check the box on various playlists to have them available for offline play.
I used to use an andoid app that would allow me to search for a song and then pick one of the results and download it. For the life of me, I can't remember its name. I don't have it on my new phone. It was basically something that would torrent music and the songs you were downloading was of 'questionable legality'. So I'm pretty confident that's why it got pulled from the Google Play store and you had to search out and install the APK separately.
happy mod
Now that I have spotify, I'm pretty happy with its ability to do offline play. In fact, I can have music saved on my laptop at home, then go into spotify and select some of those songs/directories for "local playback". Then I can create a playlist with those local songs, and in turn go to my phone and pull up that same playlist and select it as available for offline play. BAM. I've just taken music stored on my home laptop and made it available to play via spotify on my phone even when I don't have a data connection.