FTP servers at that time for MP3s were ratio servers. You had to upload something in order to download and at a specific ratio of kb. Most wouldn't give you credit for uploading something they already had as well.
Finding the songs was no problem. I can remember some kind of web search engine. It was just too hard to get a collection going to even be able to download something though. I guess the idea was to rip your cd collection but that idea simply didn't occur to me at the time.
Napster took off because it was a free record store at a time when everyone was use to paying $13 an album in 2000 USD($23 adjusted for inflation).