Solving “locale: Cannot set XXX to default locale: No such file or directory” in Debian 7

I just received a new server, where this site will eventually get moved, yet it was provided with a little error about the locale. More specifically, each time I’d run apt-get to install or uninstall stuff, I’d get the following error message:

locale: Cannot set LC_CTYPE to default locale: No such file or directory
locale: Cannot set LC_MESSAGES to default locale: No such file or directory
locale: Cannot set LC_ALL to default locale: No such file or directory

(NB: it can also be reproduced by running locale -a)

After a brief search, I found that this was caused by an incomplete setup of locales. Basically, the steps to solve this are:
nano /etc/locale.gen
Then edit this file (it’s a commented list of all possible locales, I believe), uncommenting the locale you want. When you’re done, run:
locale-gen
Which will generate the locale files for the selected locales. The output will look like:

root@80-5-13-213:/etc# locale-gen
Generating locales (this might take a while)...
  de_DE.UTF-8... done
  en_US.UTF-8... done
Generation complete.

That’s pretty much it, the errors should be gone now. I had this error in Debian 7 but my guess is it’s fairly similar for many distros. For instance the page where I read about the solution presented it for Arch Linux.