I used AltaVista and Hotbot all the time, as well as other search engines and curated pages, and there was no problem finding things. I believe most people used search engines and aggregation pages since entering the address in the browser bar would simply yield an error if you entered it wrong. Connecting the address bar to a search engine is fairly recent and was disputed a lot.
Google did nothing particularly innovative or new, they just had the cleanest interface, their page was fast, and provided good results. That's what made them successful.
Edit: On a side note, I feel really old now. :(