They used the naive approach: you searched for "steak", and they would bring the pages which included the word "steak".
The problem is that people could fool these engines by adding a long sequence like "steak, steak, steak, steak, steak, steak" to their site -- to pretend that they were the most authoritative page about steaks.
Google's big innovation was to count the referrers -- how many pages used the word "steak" to link to that particular page.
The rest is history.