So you weren't a normal, mainstream, new user to the internet. You knew how to use it, you knew where to go to search.
I was the same in the 90s (minus Gopher skills), I learned about Yahoo, Altavista, Infoseek, etc. and became a wizard to my friends and some relatives because I could find things on the internet, didn't need to know the website address beforehand or click somewhere in AOL.
It did exist, it just wasn't accessible and generally available, nor it was a tool people knew how to use.
So domain names up to the early 2000s were pretty important to capture the mainstream market, not the Gophers.
Prior to that people would at least need to sit down and dedicate attention to whatever they were doing online at their desktop.
It required at least some technical base knowledge.
While nowadays pretty much everybody can, and will, pull out their smartphone even during very short breaks: It' all short attention span, relegated to devices were multi-tasking is way more of an hassle, which means people are also way less likely to do research on whatever they are discussing.
It's gotten to a point where in many places writing anything longer than Tweet length is considered something bad, as most peoples attention span just can't cope with long-form forum posts anymore.
Google and Pagerank changed all that, but up until then, it was all very tricky and each search engine had its niche- Yahoo with its directory, Ask Jeeves had a user friendly interface, lycos and altavista had some niches of their own as well that I can't quite recall- or maybe they just each had brief shining moments in the sun. At one point I had desktop software that was a meta crawler that would enter a query into each one. The full text searches on keywords that may or may not really be relevant to what you wanted were really not all that good.
People started to understand how PageRank worked, and managed to get George W. Bush's official biography page at whitehouse.gov to the top of the search for "miserable failure." As I recall, this worked until at least 2008, maybe a couple years past that.
We typed in a few things, but it didn't go anywhere.
I remember he called the browser a "web crawler", which was probably the search engine someone told him to use to find sites. We had no idea.
Otherwise, I have a lot of memories exploring the web by typing in words followed by TLDs and writing down the interesting ones. It was another year or two before aggregators cropped up, copying and returning the first ten results of any manual index.
I could gopher topics by early 90's, and Infoseek, Yahoo, WebCrawler, etc. were a full text search of pages by mid 90's.
I distinctly recall searching usenet across multiple servers.
Even before this, when data only flowed through uucp (or Fido), search was albeit queued, readily available.
Your mileage may have varied; i just want to be clear that it was not that it did not exist, but new-comers would have a steeper learning curve. Today, it is expected, nay, demanded as a human right to be able to search the entire internet from a uniform and single klick search box. (yes, old crotchety, "in my day..." :) )
(edit: misspelurating stuffage)