Is it possible to set Gnome Terminal's title to "user@host" for whatever host I'm connected to?

Yes. Here's an example for bash using PS1 that should be distro-agnostic:

Specifically, the escape sequence \[\e]0; __SOME_STUFF_HERE__ \a\] is of interest. I've edited this to be set in a separate variable for more clarity.

# uncomment for a colored prompt, if the terminal has the capability; turned
# off by default to not distract the user: the focus in a terminal window
# should be on the output of commands, not on the prompt
force_color_prompt=yes

if [ -n "$force_color_prompt" ]; then
    if [ -x /usr/bin/tput ] && tput setaf 1 >&/dev/null; then
        # We have color support; assume it's compliant with Ecma-48
        # (ISO/IEC-6429). (Lack of such support is extremely rare, and such
        # a case would tend to support setf rather than setaf.)
        color_prompt=yes
    else
        color_prompt=
    fi
fi

TITLEBAR='\[\e]0;\u@\h\a\]'
# Same thing.. but with octal ASCII escape chars
#TITLEBAR='\[\033]2;\u@\h\007\]'

if [ "$color_prompt" = yes ]; then
    PS1="${TITLEBAR}\[\033[01;32m\]\u@\h\[\033[00m\]:\[\033[01;34m\]\W\[\033[00m\]\$ "
else
    PS1="${TITLEBAR}\u@\h:\W\$ "
fi
unset color_prompt force_color_prompt

Also note that there can be many ways of setting an xterm's title, depending on which terminal program you are using, and which shell. For example, if you're using KDE's Konsole, you can override the title setting by going to Settings->Configure Profiles->Edit Profile->Tabs and setting the Tab title format and Remote tab title format settings.

Additionally, you may want to check out:

• this "How to change the title of an xterm" FAQ for other shells
• this "Prompt Magic" tip for a good reference of the escape sequences that work in bash.
• this Bash Prompt HOWTO for a reference on ANSI Color escape sequences.

Here's a version of the SSH bash script that I use which sets the remote server's title and command prompt without making any changes to the remote server.

my_ssh.sh:

#!/bin/bash
SETTP='MY_PROMPT="$HOSTNAME:$PWD\$ "'
SETTP="$SETTP;"'MY_TITLE="\[\e]0;$HOSTNAME:$PWD\a\]"'
SETTP="$SETTP;"'PS1="$MY_TITLE$MY_PROMPT"'
ssh -t $1@$2 "export PROMPT_COMMAND='eval '\\''$SETTP'\\'; bash --login"

You can invoke it by calling ./my_ssh.sh username hostname