The used locale is set via environment variables for the process (like the shell running in your terminal).

Most of the time it is sufficient to just change LANG, assuming you use bash

$ export LANG=en_GB

Put this into your ~/.profile file to make it work for all (even non-terminal) processes.

You can have a look at /usr/share/locale/ for some list of locales.

It's an interesting question, but I think there may be a misconception in there about how variables are set up. When a secure shell session is initiated (ssh remotehost), what happens at the other end is an instantiation of a new shell with a separate environment. That is a fancy way of saying that the server starts a fresh shell. That new shell may or may not be configured with the same locale as your original local shell.

E.g

geee: ~
$ echo `locale |grep LANG` :: `date`
LANG=en_US.UTF-8 :: Mon Dec 3 07:04:00 CET 2012

$ ssh flode
flode: ~
$ echo `locale |grep LANG` :: `date`
LANG=nb_NO.UTF-8 LANGUAGE=nb_NO.UTF-8 :: ma. 03. des. 06:59:33 +0100 2012

In order to demonstrate this, I set up the locale on the remote shell for Norwegian by adding the following lines to the ~/.bash_profile file:

export     LANG=nb_NO.UTF-8
export LANGUAGE=nb_NO.UTF-8
export   LC_ALL=nb_NO.UTF-8

Similarly, you will have to set up the environment on the remote shell to do the same. Of course, other shells read different startup files such as ~/.zprofile for the Z shell.

The misconception I suspected lay in that the local variables (settings) are in no way forwarded. The remote shell has its own settings. In order to list the available languages on the remote host, be it a minimalistic BusyBox shell or a full-blown GNU OS, use the locale command with the -a switch (as noted in the question). Any of the printed lines may be used as a locale setting for that environment.

As for the first question, the default locale that any shell starts with is usually configured in a central place such as /etc/profile. Most login shells read this file on startup.