My brother spent some time as a product manager at Alta Vista and as he put it, the Holy Grail for a search company is to become navigation, not just search. Despite an early lead, Alta Vista never managed it. People went to Alta Vista to find results, not as a general jumping off point for the web. On the other hand, I believe that Google has begun to make the transition from search tool to navigation tool.
Ultimately the navigation question is one of speed and efficiency. What will get you where you want to be on the web as quickly as possible? I find it more efficient to type "American Airlines" into Google than to try to remember if it's www.americanairlines.com or www.americanair.com or www.aa.com (and that doesn't even take into consideration the fact that even if I knew the URL, I'd likely misspell it). As a result of this shift in my thinking about Google, it has become an invaluable navigation tool.
The Google navigation experience has unquestionably been aided by integration with the web browser and the operating system itself. The Google toolbar on Explorer for Windows and the built-in Google search box on Safari for the Mac make a Google search one click closer and temporally top of mind. Better yet, a senior developer from Google recently turned me on to another great tool called Dave's Quick Search Deskbar. The Deskbar creates a search box in the Windows task bar that allows you to directly launch Google searches from the desktop (or searches of Ebay, Yahoo, Amazon, etc.). What's more, if you're confident that your search will land you where you want to be, just put a bang ("!") at the end of the search and you've done the equivalent of hitting the "I'm Feeling Lucky" button. The result is an incredibly efficient navigation tool that uses Google as its intermediary.
I've got to hand it to the folks at Google. It is not happenstance that has led to them making the leap from search to navigation. They have done it by both creating their own navigation tools and by producing a relatively simple API to allow third parties to access the search database. As a result, Google the upstart has managed to infiltrate the browser and the desktop -- the domain that behemoth Microsoft has so jealously guarded for years. It just goes to show that superior technology and a bit of cleverness can still be used to challenge even the strongest of competitors.