GAIM supports many protocols, including ICQ, AIM, MSN, Yahoo, and others. You have to install GAIM itself and then each protocol support individually.

I'd suggest that you get a jabber account and then you can complement, via the Jabber "gateways", the use of Gaim and the use of the Messaging tools already present on the Nokia N800 (mainly initially Google talk oriented) and have total full messaging capability from your Internet table.

Cheers