Before Google, we actually made do with other search engines. I used mostly Yahoo! and Lycos. But there were many more.
Around that same time, there were Webrings. At first, they were just segments of HTML at the bottom of the page that would link to the next site on the same topic. When sites were edited manually, this was a tedious practice.
A webring (or web ring) is a collection of websites linked together in a circular structure, and usually organized around a specific theme, often educational or social. They were popular in the 1990s and early 2000s, particularly among amateur websites.
Source: Wikipedia
Over time, automation was introduced and web site could link to the webring using JavaScript. This gave administration of the webring to the owners of the webring tools, rather than the individual sites.
Typical Webring Layout
The whole idea was to "spread the traffic." When users reached the bottom of the page, they'd find the webring interface to bring them to more web sites on the same topic. The hope was that popular sites would include the webring which would lead to less popular sites.
The problem was, there really wasn't a whole lot of incentive for popular sites to join a webring. So often, only low traffic sites would bother to join. Sometimes, a low traffic site would have more traffic over time and never remove the webring, so there was always the chance that it would eventually work as intended.
These days, most webrings are just a shell of broken links. They're mostly a remnant of forgotten pre-SEO cruft from a 20 year old practice.