Google simply returned significantly better search results than the competition.
Other search engines at the time would do a full text search and return all web pages that contained the text you wanted, just like how you would search for a document on your computer. The pages where the word appeared more often would rank higher. This was a terrible signal, and could be very easily gamed (for example by adding invisible lists of words and phrases at the bottom of the page, which you can still find on very old sites).
Google was the first to use the concept of *backlinks*. They realized that your page was more important if other pages were linking to it. By creating this graph of links for the entire web, they were able to magically surface high quality results just by using a fundamental property of the internet – hyperlinks. (This is also why an early codename for Google was “backrub”).
Latest Answers