The big reason for me was that it "just worked". Altavista was the biggest player at the time but you had to learn a while query language to get good results. Google's search engine took plain English keywords and have relevant results.