[PhilB]

Я так полагаю, необходимо установить кодировку для кластера перед созданием базы с помощью initdb (в debian это /usr/lib/postgresql/8.4/bin/initdb).

Из документации
"Locale support is automatically initialized when a database cluster is created using initdb. initdb will initialize the database cluster with the locale setting of its execution environment by default, so if your system is already set to use the locale that you want in your database cluster then there is nothing else you need to do. If you want to use a different locale (or you are not sure which locale your system is set to), you can instruct initdb exactly which locale to use by specifying the --locale option. For example:
initdb --locale=sv_SE"

Видимо в вашем случае, в locate надо указать ru_RU.KOI8R

Подробности в официальной документации (пакет postgresql-doc) в разделе "22.1. Locale Support".

P.S. Переименуйте тему. Программа правильно называеть либо postgres, либо postgresql.