Настраиваем языковые параметры:
dpkg-reconfigure locales
Включаем локали "ru_RU.CP1251 CP1251" и "ru_RU.UTF-8 UTF-8". По-умолчанию выберем UTF-8.
При следующем подключении к серверу по SSH проверяем:
locale