Bem, a maioria dos usuários de KDE já utilizam a ferramenta Katapult, um lançador de aplicações. No caso do Gnome, pode ser usado o Gnome-do, que é uma ferramenta inteligente que torna a execução de tarefas comuns no seu computador simples, eficiente e divertida. Não só lhe permite procurar itens no seu desktop (por exemplo, contatos, favoritos, imagens, música), como também permite que você especifique ações para realizar sobre os resultados de pesquisa (por exemplo: abrir e-mail, chat, play).

Fica aí a dica:

# apt-get install gnome-do

Depois Alt + F2 e digite: gnome-do

A tecla de atalho padrão dele é (super+espaço).

O ideal é configurá-lo para inicializar junto com o sistema, pra isso vá em:

Menu / Sistema / Preferências / Sessões

Vá em ADICIONAR:

Nome: Gnome-do
Comando: gnome-do Referência: http://do.davebsd.com/index.shtml

Espero que seja útil.