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)