For CentOS or Amazon AMI Linux, add these lines to /etc/environment (create it, if it doesn’t exist):
LANG=en_US.UTF-8
LC_ALL=en_US.UTF-8
To edit this file via SSH console, try
sudo nano /etc/environment
Edit
For Debian-related distributions (Ubuntu, etc.), you should check that /etc/default/locale is empty. That’s the outcome of choosing None in dpkg-reconfigure locales which is suggested if users access via SSH (see Debian Wiki).
/etc/environment is deprecated since Debian Lenny (5.0).