Pidgin, Trillian and Adium are great IM softwares. Off The Record is a plugin for those programmes which enables encrypted communications with Perfect Forward Secrecy using standard clients such as Google Talk, ICQ, AIM etc.
Trillian now has an iPhone version. It is very important that an OTR application, or similar technology, is developed for mobile platforms like iPhone and Android so that people might have secure mobile communication.
*UPDATE: It recently came to our attention that Pidgin Saved Passwords are saved in plain text in an obvious location. Thus, anyone gaining access to the user's filesystem can obtain all their IM passwords, including their Google Account if they use it for Google Talk. This is a major security vulnerability. Be aware!