You must've been somewhere nice that had fast internet. I think most people back then had dialup, and downloading a single song would take at least 20 minutes on their 28.8k modem.
You just waited that long to download music. That was all there was to it. MP3 was mindblowing when it was first released, in terms of how good it sounded for the size.
Obviously many people just ripped their own CDs. Many CD-ROMs didn't support ripping CDs at a data level - so you had to rip in real-time via analog! Crazy.
Most people I knew had 56k modems by 98 (by '99 I had a cable modem), 128kbs compression was the standard you'd find, and getting a song for free by just waiting 15 minutes was still magic
Edit almost forgot about Ethernet in the dorms. I picked my college because of high speed Internet.
As mech4bg said, much or most of people's .mp3 libraries at that point had probably come straight off CD. Napster wasn't even released until 1999, and "Rip. Mix. Burn." was Apple's edgy new slogan of 2001 http://www.youtube.com/watch?v=4ECN4ZE9-Mo .
Wow, that's quite a find. A rare artifact from the pre-iPod, pre-iTunes Store tip of Apple's foray into digital media, and a strong piece from Apple's agency at the time.
You just queue up a bunch of stuff using a download manager[1] and stay connected for longer. Come back the next day (or two or three) and voila! The good managers would even resume partial downloads if the connection dropped (which it always did).
Audiogalaxy was our savior. Search from any computer and queue up the download to your satellite. When you arrived home 5-6 hours later your music would be waiting for you.
Obviously many people just ripped their own CDs. Many CD-ROMs didn't support ripping CDs at a data level - so you had to rip in real-time via analog! Crazy.