A combination of shelves (for all of the non-digital music) and external hard drives (a Thermaltake BlackX dual-HD setup). The external hard drives are used essentially for backup. I have 124.2 GBytes of music on my regular hard drive (including paid-for .zip and .rar files which were downloaded from various sites). However, most of the files are .flac files which I ripped from CDs which I own. The external hard drive is usually off, although I sometimes leave it on.
The idea behind backing them up on an external hard drive is so that I do not have to rip them all again whenever I install a new version of an operating system (usually every six to twelve months). However, all of the .zip and .rar archives files are also backed up on DVDs, so that they don't get lost in case of a hard drive failure. I update a folder named "NewMusic_{date}" on the external hard drive every couple of months, so the backup is kept pretty much up to date.
If it ever comes to not having enough space on my internal hard drive, I would probably just keep the music that I listen to most of the time on the internal hard drive, and copy any other music onto my internal hard drive if I wanted to listen to it.
Also, music that I listen to frequently is put into "play lists", and these are also backed up. By "play lists" I mean that I copy the actual files into a "play list" folder and then save those folders. Then those songs are put into actual playlists for Amorak, or whatever other audio players.
This sounds pretty complicated, but I don't find it so, and I have been using this system for a couple of years now.