I've recently become interested in lightening my electronic footprint. In that line, I'll give you a quick list of the programs I've been playing with.
Instant messaging: For real anonymity, you want the gaim-otr Plugin. Adium already has OTR in it. OTR stands for off the record, and offers the highest privacy you could have in an online conversation, including most significantly, deniability - the other person can provide no subsequent proof that you said what you said. That's what I call privacy! A number of *nix distributions provide a package of gaim-otr, so you can just install it, namely Arch, Debian, Fedora, FreeBSD, Gentoo, NetBSD and linuxpackages.net for Slackware. If you didn't know, you can easily check package availability using the whohas tool.
Note that the current version of OTR has a flaw in it, but this will be fixed soon.
Browsing: The typical approach to make browsing untrackable is to use the tor proxy, which is actually an encryption and redirection technology, which allows traffic to be bounced through a series of onion servers, so that traffic appears to come from one of those servers rather than the user. Privoxy is a front-end to the tor client, and provides some further privacy filtering. A good summary and installation instructions for Firefox on Windows (Linux, for one, is very similar) can be found here. You can also use tor as a proxy for other internet services, such as IRC - the article describes how.
I think the fact that tor is an anagram of otr is accidental, but I'm not sure what tor stands for - something onion routing? Tor, again, is available for quite a few *nixes, namely Arch, FreeBSD, NetBSD, OpenBSD and Source Mage Linux, as well as Mac OS X through DarwinPorts.
There was at one point a LiveCD by the name of Privacy Knoppix, and I read somewhere (but can't find it, please let me know!) about a distribution of portable Firefox with Privoxy and tor - incredible amounts of privacy for internet café usage!
Email: Now, this is an old one, and most of you will know that the way to be safe is with Thunderbird, Enigmail and GPG (or gnupg, as packages are sometimes named). You'll find plenty of instructions by googling for those keywords. I could only find packages for enigmail in Debian and FreeBSD - I suspect this may be due to it having another package name; gnupg, however, is ubiquitous.