They did the right thing at the right time. When it was first launch, it solved a problem: How could an average user find things on the internet in an easy, non threatening way?

Pre Google, search engines were designed with horrible UI's, plastered with ads, pop ups, and they didn't return very relevant results. Seriously, I was a heavy internet user in those days and the search engines out there were TERRIBLE. It was just understood that to find what you wanted, you had to use at least 3-5 searches on multiple different search engine. There was even a search engine that search other search engines (Metacrawler) to try and make this easier. It made using the internet a frustrating, non useful experience for novices.

Then along comes Google. A clean, blank screen with a logo and search bar. That was it. You typed what you wanted, and got the result you were looking for. It was simple, non frightening, and it worked. For the first time your grandmother could figure out how to search the internet all on her own. It simply dominated every other search engine in terms of usability and functionality, and they all vanished into obscurity shortly after.

This was all happening at the time the internet was really hitting the mainstream, so it just became part of the lexicon, to get information on the internet became "to Google it", and once somehting enters the lexicon like that, it's nearly impossible to dislodge