Before the search that we know of today, there were directories (see http://dmoz.org for example) where you submitted your site. Originally it was a list, then a hierarchal list, then there so many entries they let you search their database, then they crawl the web to find other sites, then they search the _content_ of other sites, so you can see how it evolved.

Web rings and pages of links to other sites were also common, basically what RG did, but more reciprocal.