Install xauth to do X over ssh

I just spent an hour trying to figure out why I could run firefox over ssh from two remote offices but not from a third. The DISPLAY variable was not set when I connected with:
ssh -X user@host

Turns out that xauth is not installed by default (on Ubuntu Server). I vaguely remember figuring that out before but never documenting it. So now I have.