GNOME Terminal's character encoding handling is broken.

For a terminal, there are 2 possibilities:

1. The terminal gets the character encoding from the current locale.

2. The terminal forces the character encoding to some settings, but
needs to change LC_CTYPE accordingly (or let the user do this).

GNOME Terminal does neither. I have UTF-8 locales, but GNOME Terminal
sets the character encoding to ANSIX3.4-1968[*] (ASCII) and lets
LC_CTYPE unchanged (en_US.UTF-8 in my case), yielding garbage with
some applications (e.g. Mutt).

[*] The Terminal → Set Character Encoding menu has the following
selected by default:

  Current Locale (ANSIX3.4-1968)

I don't know what "Current Locale" means since this is obviously
wrong.

The manual says "The default character encoding is usually UTF-8."
but this is not what happens here.

This problem doesn't occur when I run gnome-terminal on a different
machine via ssh: I get "Current Locale (UTF-8)" as expected.

I wonder whether your first machine has some leftover configuration from
an old machine, or something... my only options are "Unicode (UTF-8)"
and "Current Locale (UTF-8)", and when I click "Add or Remove..." to go
to the preferences for locale selection, ANSIX3.4-1968 (or any other way
to spell "plain 7-bit ASCII") isn't even listed as an option.

    S

No, I get the same behavior on both machines. What matters is whether
I start gnome-terminal locally or via ssh. And starting gnome-terminal
after a "ssh localhost" doesn't work at all (bug 731456).

So, the question is: how does gnome-terminal determine the
"current locale"?

Certainly not via the LC_* environment variables, as they are
the same with and without ssh. And I think that the fact that
gnome-terminal doesn't use them is a bug.

And "LC_ALL=C gnome-terminal" in a ssh session doesn't change
anything: gnome-terminal still selects UTF-8.