The dirt-simple UI and fast loading times helped.
Before Google, the dominant search engine was AltaVista, which was awful. The UI was so crowded that you had to search for the search bar, and it was so full of graphics that if you were on dialup, loading took forever unless you turned images off.
And, yeah, PageRank helped. It wasn't uncommon for you to find what you were looking for on page 3 or 4. Google had what you were looking for on page 1, always. In fact, pre-Google search was so bad that if you were looking for anything obscure, you had to use multiple search engines. When I'd get serious about finding something, I'd fire up AltaVista, Infoseek (Disney/ABC/Go.com), Hotbot, WebCrawler (AOL), etc. in separate browser windows and search on all of them. And for the lazy, there was MetaCrawler, which automated this; I didn't use it often, mostly because I kept forgetting about it, but when I remembered to use it, it was a godsend.