Настраивал в ubuntu 11.10. Для начала ставим dconf-editor:
$sudo apt-get install dconf-editor
Запускаем dconf-editor и идём в ветку org - gnome - gedit - preferences - encodings. Там правим ключи "auto-detected" на ['UTF-8', 'CURRENT', 'WINDOWS-1251', 'ISO-8859-15', 'UTF-16'] и "shown-in-menu" на ['UTF-8', 'WINDOWS-1251', 'ISO-8859-15']
После этого в gedit текстовые файлы в кодировке 1251 должны нормально открываться на русском языке.