One big issue with digitally downloaded music is music that was purchased with DRM (Digital Rights Managment). This will soon be a thing of the past as Apple is dropping DRM from iTunes, but what about the music you have already purchased that contains DRM? Your best bet for this is to burn your music to a CD and then use a tool like Grip or KAudioCreator to rip and encode the music from the CD to a suitable format. In some cases the DRM'd music will only allow you to burn the files to CD a set number of times. It's best, when downloading music from iTunes, to instantly make a backup copy of the music.
Once you're using Linux you can give services like Amazon.com a try. Amazon has a great downloader application for Linux that makes downloading DRM-free mp3 files a snap.
And it was recently announced that Apple is moving towards a DRM-free iTunes store. So soon you won't even have to worry about iTunes purchased music!