I remember in the early days of the WWW, we had a web page that listed every other web page on the internet. The entire list was only a couple of pages long. You want to search “the internet”? Just scroll down through the list.
FTP and e-mail were the big things back then. Companies and individual people would put things on ftp sites, which was a big step up from the dial-up bulletin-board systems before then. With a BBS, you had to know what number to dial. Computer magazines would have some listings. Local computer clubs would have others. Sometimes things went around by word of mouth. FTP sites were a lot of the same. You found out about them from magazines, local clubs and user groups, and word of mouth.
One thing that helped was Usenet groups. If you were interested in something, there was probably a usenet group that discussed it, and you could often find listings of ftp sites and such in that group’s messages. Back in the day, I kept a list of electronic hobbyist FTP and web sites, as well as the snail mail addresses of companies that you could mail order catalogs and parts from. It started out as a fairly short list, but grew pretty large in the early to mid 1990s. Periodically, I would publish this list in a particular usenet group related to electronics hobbyists.
The way that usenet worked was a lot different than the way a modern message board works. With a modern message board (like the SDMB), you have one sever and everyone accesses that. With usenet, every computer system that wanted to access it subscribed to it, and then that computer system received every message that went out on usenet. So you didn’t have to search for message boards, they were all there under usenet, and every system that accessed usenet had its own local copy of every single message. So if you posted something on usenet about your favorite musical group, that message got copied to every single usenet archive all over the internet. It worked that way because it was really built to send out news and messages to just a handful of computers in the early days of the internet. General purpose message boards had never been a part of its original intent.
Creating newsgroups back then also required approval, and was fairly difficult to do, with one exception, groups in the alt section of usenet. Anyone could create an alt newsgroup (there was an alt.fan.cecil-adams group at some point). Since anyone could make an alt group, this is where the general purpose and popular newsgroups often ended up. Also, because of its mostly unregulated nature, as well as its higher level of traffic, some computer administrators would choose not to accept messages from the alt hierarchy, and their usenet archives would have no alt newsgroups in them.
Searching for newsgroups was easy. You just browsed through the group names. Whatever computer system you were accessing usenet from had the entire list of groups, so you didn’t have to search multiple computers. Every group and every message was right there.