Um deutsche Locales unter PHP auf einem Linux-System zu verwenden, setzt man einfach die gewünschte Locale-Einstellung (z.B. LC_TIME) auf de_DE.utf8, und in der Regel passt das dann. Zur Not kann man sich mit dem Kommandozeilen-Parameter locale -a auch einfach die verfügbaren Locales ausgeben lassen und weiß dann Bescheid. Falls die benötigte Locale nicht installiert ist, hilft außerdem ein schnelles dpkg-reconfigure locales aus, um nicht vorhandene Locales nachzuinstallieren.
Und unter Windows? o_O
Damit niemand mehr suchen muss: Das „deutsche“ Locale für Windows-Systeme heißt German_Germany.1252
setlocale(LC_ALL, "German_Germany.1252");