Os desenvolvedores de Gnome geralmente valorizam a simplicidade em relação aos recursos, enquanto os desenvolvedores do KDE preferem mais recursos, mesmo que o programa não seja adequado para crianças de 3 anos:)
Há um tíquete antigo solicitando esse recurso. Se você tiver lido, verá que O Gedit tem algum tipo de codificação de detecção automática que, infelizmente, nem sempre é perfeita. Desde 2009, há um patch adicionando o menu Encodings, embora não pareça que será aceito. Na verdade, o 'patch' parece ser um plugin para o gedit escrito em Python - você pode ver se é possível instalá-lo, embora possa estar desatualizado.
Portanto, se você precisar desse recurso, o kate é um substituto perfeito para o gedit e possui muitos recursos interessantes, além da capacidade de alterar a codificação do documento.