icq for whatever reason is still the most popular with everyone, i generally prefer "lite" apps over that so use pidgin which is a universal imer (icq, yahoo, aim, etc)
it's included in the latest ubuntu release and can be downloaded here
http://www.pidgin.im/
