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 uses, this MSDN page provides a sample registration and describes what sorts of queries you will be handed by the shell.