Provavelmente, nautilus-actions é o que você está procurando:
sudo apt-get install nautilus-actions
Agora inicie a Ferramenta de Configuração de Ações do Nautilus. Se você não quiser clicar nos menus, basta digitar "nautilus-actions-config-tool" na janela [alt] + [F2].
Isto iniciará o gui de configuração nautilus-actions, no qual você pode configurar novos comandos ou scripts para serem executados a partir do menu de contexto. O menu "help" é bem detalhado, você pode querer dar uma olhada nele.
Para iniciar o gnome-search-tool no menu de contexto, inicie a conf-tool, pressione [ctrl] + [n] (isso criará uma nova ação), marque "Exibir item no menu de contexto do local", nomeie-o (Etiqueta do Contexto), mude para o comando "Comando" e digite "gnome-search-tool" no campo "caminho". Para iniciar o gnome-search com o caminho atual, digite '--path="% d"' na caixa "Parâmetros" (veja "legenda" para outras variáveis). Às vezes é necessário reiniciar o nautilus para que as ações apareçam (nautilus -q).
Algumas pessoas tiveram problemas com a versão do repo do Ubuntu 11.10. Se você tiver problemas ao iniciar ações do nautilus, instale a versão mais recente aqui: link
Exemplo para o pacote amd64:
wget http://launchpadlibrarian.net/84698667/nautilus-actions_3.1.4-1_amd64.deb
sudo dpkg -i nautilus-actions_3.1.4-1_amd64.deb