If you wonder why
$ php -r "setlocale(LC_TIME, 'de_DE.UTF-8'); echo strftime ('%A %e %B %Y', mktime (0, 0, 0, 12, 22, 1978));"
gives you Freitag 22 Dezember 1978 on most systems like f.e. openSuSE and Ubuntu, but Friday 22 December 1978 on Debian, you need to remember that the Debian guys outsmart everything and everybody with a shell script and a configuration file, just to keep your installation lean and clean.
In this particular example, edit /etc/locale.gen and add de_DE.UTF-8 UTF-8 (or anything else listed in /usr/share/i18n/SUPPORTED), hit save and then execute
$ sudo /usr/sbin/locale-gen
and voila, the above PHP call (and everything else which requests a German locale) works!