Para sua sorte, tualatrix fez um pequeno hack no gnome-terminal e adicionou suporte para pesquisar no Google ao clicar com o botão direito em uma mensagem.
Você precisa adicionar um PPA de terceiros para que funcione. Execute estes comandos em um terminal:
sudo add-apt-repository ppa:tualatrix/personal
sudo apt-get update
sudo apt-get install gnome-terminal
Uma vez atualizado, feche todas as janelas do terminal e reabra novamente. Ele funcionará como pretendido.