Marketwatch, reporting from the D4 conference, quotes Bill Gates discussing Google as "very much the leader" contrary to Microsoft having made previous grand statements about matching Google within 6-months far longer ago. Bill Gates announced "it's a five year battle." The plan is to get users to navigate to Microsoft search rather than Google.
Microsoft has invested heavily in search, and search (among other Web services) will see an increase of $2 billion more in investment over the next year than what was initially planned. And when it all comes together, the plan is to spend on advertising to let people know. Their investment in advertising to date hasn't led to much of a market shift yet.
Postscript From Danny: Microsoft, of course, has indeed already spent heavily to promote its search service, such after MSN Search launched with Microsoft's own technology or with a recent online game promotion. But perhaps Gates means that Windows Live Search won't get the same treatment until they feel the quality has improved.