При отображении строк в RRD используется кодировка UTF-16, в которой есть
таблица русских символов,
соответствующая таблице CP1251, только со смещением.
Чтобы rrdgraph смог отображать русские символы на графиках 
необходимо внести изменения в файл src/rrd_afm.h. Находим в нем строчку

   #define afm_fix_osx_charset(x) (x)

и заменяем на

   #define afm_fix_osx_charset(x) \
     ( (x) >= 128 && (x) <= 255 ? (x) + 0x0350 : (x))

Таким образом, если в строке встречается символ с кодом между 127 и 256, то к
нему применяется смещение 0x0350.
Строки необходимо записывать в CP1251 (я использую vim с libiconv).

Для работы с KOI8 необходима еще таблица перестановок из KOI8 в CP1251

Для этого в файл src/rrd_afm.c добавляем описание таблицы
const unsigned char afm_koi2win[128] = {128,129,130,131,132,133,134,135,136,
137,138,139,140,141,142,143,144,145,146,147,148,149,150,151,152,153,154,155,
156,157,158,159,160,161,162,184,164,165,166,167,168,169,170,171,172,173,174,
175,176,177,178,179,180,181,182,183,184,185,186,187,188,189,190,191,254,224,
225,246,228,229,244,227,245,232,233,234,235,236,237,238,239,255,240,241,242,
243,230,226,252,251,231,248,253,249,247,250,222,192,193,214,196,197,212,195,
213,200,201,202,203,204,205,206,207,223,208,209,210,211,198,194,220,219,199,
216,221,217,215,218};

а в src/rrd_afm.h такие строки

   extern const unsigned char afm_koi2win[128];
   #define afm_fix_osx_charset(c) \
     ( (c) >= 128 && (c) <= 255 ? afm_koi2win[(c) - 128] + 0x0350 : (c))