gconf-editor
Перейти в /apps/gedit-2/preferences/encodings
Правой кнопкой по ключу auto_detected
Видим там пункт WINDOWS-1251 и перемещаем его выше так чтобы выше него был только UTF-8
Если этот пункт не видим то создаем его.
Ну вот как-то так.
Зы: поиск рулит, и вообще пару темами ниже схожая тема:)