Nikita Borisov and Ian Goldberg have released Off-the-Record Messaging (http://www.xelerance.com/mirror/otr/), an IM plugin for private communication providing not only the usual encryption and authentication, but also deniability and perfect forward secrecy. Deniability avoids digital signatures on messages (while preserving authenticity and integrity), so there is no hard-to-deny proof you wrote anything in particular; in fact, there is a toolkit to help people forge messages, making it extra-hard to pin things on you. Perfect forward secrecy means that your past messages and conversations remain protected even if your keys are compromised. You can read the OTR protocol description, download the source code for the gaim-otr plugin, or grab a gaim-otr binary package for Debian or Fedora Core.