Инструкция (тестировалось на Kubuntu 7.04)

а) Все начинается с генерации локали ru_RU-KOI8-R, делается это
командой locale-gen. Список локалей, которые она будет генерировать,
находится в файле /var/lib/locales/supported.d/local.

Нужно привести его к такому виду:

#cat /var/lib/locales/supported.d/local
ru_RU.UTF-8 UTF-8
ru_UA.UTF-8 UTF-8
ru_RU.KOI8-R KOI8-R

Затем, собственно, сгенерировать:

#sudo locale-gen
Generating locales...
ru_RU.KOI8-R... done
Generation complete.

б) Далее, обновляем переменные окружения. За это отвечает
файл /etc/default/locale. В нем пишем:

LANG="ru_RU.KOI8-R"
LANGUAGE="ru_RU:ru:en_GB:en"

Иксы уже сейчас будут работать с богомерзской KOI8-R, а чтобы
заставить работать консоль, нужно сделать еще несколько телодвижений:

apt-get install console-cyrillic

В файл .profile добавляем:

loadkeys /usr/share/console-cyrillic/ru-koi8-r.kmap
consolechars -f /usr/share/console-cyrillic/UniCyr_8×14.psf -m /usr/share/console-cyrillic/koi8-r.acm.gz

Готово.

p.s. Только не спрашивайте, зачем кому-то в 21-м веке понадобилась
KOI8-R. Иногда бывает, что с ней живется проще.