Acabei de instalar o Localização / Substituição Avançada (Simplesmente baixei advanced_find-3.6.0. tar.gz, extraiu e usou o plugin bash ./install.sh no terminal) para gedit 3.18.3 no Ubuntu 16.04 LTS. Parece que a instalação foi bem sucedida: 
Infelizmente,nãoconseguiencontrá-loemnenhumlugardobarparausá-lo,mesmodepoisdereiniciarocomputador:
Você poderia me ajudar? Obrigado antecipadamente!
Parece que este é um problema conhecido do Gedit v3.12 +. Veja aqui: Suporte para o Gedit 3.12 . Existe uma possível correção aqui: Não é possível carregar o plug-in .
A propósito, o projeto parece desatualizado. O último lançamento foi 2013-05-01 para o Gedit v3.8.