В Linux есть стандартный клиент. Он не только icq поддерживает но и другие меседжеры. Вроде IM называется, точно не помню. Если он у тебя еще не установлен, тогда заходишь в установку\удаление пакетов, смотришь программы для интрернета, ставишь галочку и устанавливаешь