Gaim, hands down for availabilty. Isn't Gaim included in most distros? This fact is probably where most of its popularity lie, but Gaim still beats most (if not all) other 'nix messaging apps simply because gaim just works, and it works well for many many clients (msn, yahoo, jabba etc.)
Gaim was even featured in APC (assuming you all know what apc is? if not then its a magazine (APC=australian personal computing) that also circulates around NZ and usually includes a different distro with each release and articles about certain 'nix applications and getting things to work etc.)

Bitlbee! It rocks the hizouse!

Software selection is always a matter of opinion, of course, but I have never understood why GAIM always wins these polls. I don't like it. Never have. It feels very clumsy and awkward to me, especially since I use KDE in favor of GNOME.

My choice has always been Kopete. I think it beats all the IM clients on Linux, as well as those for Windows and Mac OS-X. IMHO, it is very clean, well organized and has all the features I want.