Преступим, открываем консоль, и вводим:
sudo apt-get install qutim
После установки, запускаем допустим Qutim затем вводим ваш логин и пароль от системы, после чего Вам представиться диалог выбора протокола, нам понадобиться протокол MRIM (mail.ru агента).