deskbar-applet - universal search and navigation bar for GNOME\nestraier - a full-text search system for personal use\ngooglizer - utility to search Google via your GNOME menu/panel
Sorry nothing in Debian for KDE yet, though there are things creeping into the light:
[link|http://linux.softpedia.com/get/Desktop-Environment/Tools/Kat-Desktop-Search-Engine-for-Linux-2138.shtml|KAT]
In Kubuntu, you might try apt-cache search google, to come up with somethings that are in (K)Ubuntu and not Debian.