I was getting really annoyed getting these messages while managing my Debian and Ubuntu VPSes
perl: warning: Setting locale failed.
perl: warning: Please check that your locale settings:
LANGUAGE = (unset),
LC_ALL = (unset),
LANG = "en_US.utf8"
are supported and installed on your system.
perl: warning: Falling back to the standard locale ("C").
Turns out the solution is simply to run these commands
apt-get install locales
The export lines above can also be saved into either ~/.profile or ~/.bashrc or ~/.cshrc