sudo apt-get install recode recode CP1251..UTF8 file.txt
где:
CP1251 — кодировка в которой сейчас находится файл;
UTF8 — в какой кодировке файл должен быть;
file.txt — файл, который нужно перекодировать.
Открываем файл в «родной» кодировке:
gedit --encoding windows-1251 file.txt
в меню gedit выбираем Файл — Сохранить как….
В открывшемся окне указываем нужное имя файла и нормальную кодировку.