Google delivers good results. When you do a search on Google, the search engine scours the web and brings back what it determines is relevant, content rich, websites. Most of the time, Google brings back something you can use. It has a massive database of sites, so it gives you a lot of sites to choose from, and does it extremely fast.
Google became famous from the advertisement point of view and even today 80% of its revenue is from advertisement.
Sergei Brin and Larry Page both did graduate-level work on search technology which broke new ground. They were in the right place at the right time to get onto massively parallel computing just as it was really becoming feasible, and built inexpensive datacenters with outrageous computing resources. A major part of Google's success was that Page and Brin spent damn near all of their investors' money on the actual technology instead of on cars, hookers, and blow. You know, like the rest of the dot-com kids. The rest of it was that Page and Brin honestly cared about doing the best damn job they could, and never kicked back saying "that's good enough, the competition will never catch up." The one and only reason Microsoft gives a tinker's dam about search is that it's the only place they have anything remotely approaching a worthy competitor. Google doesn't lie, cheat, or steal for their success: they work their arse off for it, and they get every scrap of it honestly.
I totally know what you mean and to me it is seriously a miracle. A lot of people responding to this thread claim that adsense is responsible for Google becomming so well known but what about the time BEFORE adsense, adwords, etc. that Google was still dominating search engines? Maybe it's the catchy name... "Google it." rolls off the tongue and sounds trillions of times better than "Yahoo it." Haha. You might actually get someone to say "Bless you." after saying the latter XD
Google may get so big that the federal government will step in one day and bust them up using the Anti-Trust laws, like they did with Standard Oil in the 19th century and Microsoft in the 20th century. No more monopolies.