As I remember it (I was just starting college at the time), Google search was an absolute revelation. You could type in a search term and the first hit would usually be what you wanted. AltaVista required a lot of looking through results to find the right thing and messing around with boolean operators. People switched over and never looked back. Google went from zero to a substantial majority market share in only about one year.