Pyrite foi escrito apenas para este propósito. Ainda não está empacotado - portanto, não nos repos; você terá que seguir algumas instruções para baixar e extraí-lo para um local de sua escolha manualmente, mas funciona maravilhosamente IMHO. (Eu diria que embora ... desde que eu sou o desenvolvedor.)
Como bessman mencionou, seahorse-nautilus é o caminho a seguir se você quiser criptografar arquivos assimetricamente no navegador de arquivos. (Além do texto, pyrite pode fazer criptografia simétrica e assimétrica de arquivos, mas não está integrado ao Nautilus.)
Por fim, confira a resposta a essa pergunta anterior para mais detalhes sobre a configuração de gedit com gpg .