sudo apt-get install recode
recode CP1251..UTF8 file.txt

где:
CP1251 — кодировка в которой сейчас находится файл;
UTF8 — в какой кодировке файл должен быть;
file.txt — файл, который нужно перекодировать.

Открываем файл в «родной» кодировке:

gedit --encoding windows-1251 file.txt

в меню gedit выбираем Файл — Сохранить как….
В открывшемся окне указываем нужное имя файла и нормальную кодировку.