Team MoDaCo has a tweak that will enable a search button in the navigation keys for the Galaxy Nexus. I'm definitely glad this is being implemented. I like having the search button at the bottom.
Link: Galaxy Nexus Receives UI Patch, Adds Dedicated Search Option To Lower Menu Bar
Link: Galaxy Nexus Receives UI Patch, Adds Dedicated Search Option To Lower Menu Bar