I was stumped why I couldn't run X11 software on my Ubuntu server installation and have it forwarded through my SSH connection to my desktop Windows machine running Xming.
The solution was to install the xauth package from the Ubuntu repositories:
$ sudo aptitude install xauth
Apparently installing an X11 application (gitk) didn't pull in that dependency.
Now I can finally run gitk and visualize those complicated git graphs. Yay!