Off-the-Record Messaging
Thanks to a friend of mine, who uses Mac, I recently discovered 'Off-the-Record Messaging':
Off-the-Record (OTR) Messaging allows you to have private conversations over instant messaging by providing:
Encryption
No one else can read your instant messages.
Authentication
You are assured the correspondent is who you think it is.
Deniability
The messages you send do not have digital signatures that are checkable by a third party. Anyone can forge messages after a conversation to make them look like they came from you. However, during a conversation, your correspondent is assured the messages he sees are authentic and unmodified.
Perfect forward secrecy
If you lose control of your private keys, no previous conversation is compromised. Source
Simply install the pidgin-otr plugin through Synaptic, activate it in Pidgin and you can chat securely. (You can exchange 'fingerprints' with your friends and verify them).
Some more info from Wikipedia:
Off-the-Record Messaging, commonly referred to as OTR, is a cryptographic protocol that provides strong encryption for instant messaging conversations. OTR uses a combination of the AES symmetric-key algorithm, the Diffie-Hellman key exchange, and the SHA-1 hash function. In addition to authentication and encryption, OTR provides perfect forward secrecy and deniable encryption. This is different than the "off the record" setting in Google Talk, which merely disables logging.