I just learned about off-the-record, a plugin for Gaim which “Just Works”. apt-get install gaim-otr should do the trick on Ubuntu or Debian, then go into the plugin configuration list in Gaim and generate keys for the accounts you want to use it with. Voila!
One needs to do an out-of-band (voice, typically) verification of someone’s key if you want to be sure to make life hard for the man in the middle. I suspect that we’ll soon have voice chats in Gaim too, so that will be even easier to arrange. Very classy work.
Anybody care to file a main inclusion report?