In the .bashrc/.zshrc of the remote machine add this:

    echo '\033]11;#440000\007'

On the local machine add this to reset the terminal color:

    ssh () {/usr/bin/ssh "$@"; echo '\033]11;#000000\007'}