The Cyrillic X Reference

create ru_RU.KOI8-R locale. The first way to do it is to run

dpkg-reconfigure locales

or add line

ru_RU.KOI8-R KOI8-R

to /etc/locale.gen and run locale-gen script.

then add
LANG=ru_RU.KOI8-R
to /etc/environment

/etc/X11/XF86Config (XF86Config-4 in case you are running woody/testing) should contain:

Section "Files"
    RgbPath    "/usr/X11R6/lib/X11/rgb"
    FontPath   "/usr/X11R6/lib/X11/fonts/cyrillic/"
    <Other FontPath lines>
    ModulePath "/usr/X11R6/lib/modules"
EndSection

So that FontPath "/usr/X11R6/lib/X11/fonts/cyrillic/" is the first of all
FontPath lines. If you are running potato keyboard section should be:

Section "Keyboard"
    Protocol    "Standard"
    XkbRules    "xfree86"
    XkbModel    "pc101"
    XkbLayout   "ru"
    XkbOptions "grp:shift_toggle"
EndSection
If you're running woody (and Xfree4), one of "InputDevice" sections should be (make corrections to the section where you see string Driver "keyboard"):

Section "InputDevice"
    Identifier    "Generic Keyboard"
    Driver    "keyboard"
    Option    "CoreKeyboard"
    Option    "XkbRules"   "xfree86"
    Option    "XkbModel"    "pc101"
    Option    "XkbLayout"   "ru"
    Option    "XkbOptions" "grp:shift_toggle"
EndSection

shift_toggle, toggling register with two shifts. If you insert line
XkbOptions "grp:toggle", than Right Alt will toggle register, if
you insert XkbOptions "grp:caps_toggle", register will be togled by CapsLock.

/etc/gtk/gtkrc.ru:

style "gtk-default-ru" {
       fontset = "-adobe-helvetica-medium-r-normal--12-*-*-*-*-*-iso8859-*,\
                  -*-arial-medium-r-normal--12-*-*-*-*-*-iso8859-1,\
                  -cronyx-helvetica-medium-r-normal--12-*-*-*-*-*-koi8-r,\
                  -*-arial-medium-r-normal--12-*-*-*-*-*-koi8-r,*-r-*"
}
class "GtkWidget" style "gtk-default-ru"

if you use a display mandager (e.g. xdm) put line

export LANG=ru_RU.KOI8-R

in your ~/.xsession

Netscape 4.x users, you need to run netscape binary directly (otherwise read and edit maintainer's wrapper) and if you want to use cyrillic in html forms do not run xfstt (X Font Server True Type).