After debootstraping of debian you have to set the locales - "C" locales are not what we want :). At first we have to install the missing packages:

aptitude install locales language-env

Now we reconfigure the locales with

dpkg-reconfigure locales

I'd say the menu should be self explaining. I've choosen the following locales (of course I am running an UTF-8 system)

[*] de_AT ISO-8859-1
[*] de_AT.UTF-8 UTF-8
[*] en_US ISO-8859-1
[*] en_US.UTF-8 UTF-8

There is also an interesting howto for switching debian to UTF-8

Happy Hacking.