Holy cow, I wrote a book!
You may have noticed that in Windows Vista Service Pack 1,
the Search option on the right hand side of the Start menu
has been removed.
What happened to it?
It's redundant with the Search Box,
that thing that has the keyboard focus when you initially open
the Start menu.
(But if you really want to open Explorer in Search mode,
you can still type Windows+F or press F3 when focus is on the Start menu.)
And if you want to plug into the search protocol that the Start menu
this MSDN page
provides a sample registration and describes
what sorts of queries you will be handed by the shell.