Gaim and Kopete are both ICQ compatible, I believe. These usually come built-in to the GUI you choose. Kopete is specific to KDE, but I believe it will also run under GNOME so long as you have the KDE components installed. I have used both, and currently prefer Kopete because I have yet to figure out how to make GAIM log into multiple accounts at once. However, I believe GAIM offers more functionality in the long run.
Hope this helps.