Для MPlayer -- скачать и установить с его сайта русские шрифты (для субтитров).
Касаемо же общесистемного приворачивания русских шрифтов -- в местный FAQ, в раздел Документация (взять Cyrillic HOWTO). Также в зависимости от дистрибутива изучить следующее: для Slackware -- http://kmxb.narod.ru/russ1.html, для редхата -- http://mcmcc.bat.ru/rh9koi/index.html.
Я бы добавил, что можно не скачивать шрифты для субтитров - достаточно с любого web-ms шрифта типа arial кинуть симлинк под названием subtitle.ttf в ~./mplayer