Всё очень просто:
1. Устанавливаем пакет console-cyrillic:
sudo apt-get install console-cyrillic
2. Конфигурируем данный пакет:
sudo dpkg-reconfigure console-cyrillic
3. Соглашаемся с автоматической загрузкой русской консоли при старте системы