The Midnight Commander shows crap instead of umlaut characters? Command locale -a doesn't print something like de_DE.UTF-8? There is no de_DE.UTF-8 locale!
First add de_DE.UTF-8 UTF-8 to /etc/locale.gen. Then type locale-gen. Then do eselect locale list. This should now list the new added de_DE.utf8. Activate the new locale with eselect locale set NUMBER. Type . /etc/profile.