Google initially targetted a niche (geeks and nerds like us) with no-fuss, no-ads search experience where weight of the result depended mostly on how many citations it had. They were very present at conferences related to free software, for instance (which I'd consider investment in marketing).

And this group was the one in charge of "fixing their relatives' computers", so we were all too happy to tell them about Google: this is how word-of-mouth worked for them.