How to install different locales on a fresh debian installation

Simples:

sudo dpkg-reconfigure locale

This will load a GUI where you should select the new locales to install, then follow the onscreen instructions.