existem duas formas,
primeira Versão estavel
adicione o ppa
sudo add-apt-repository ppa:gnumdk/ppa
sudo apt-get update
sudo apt-get upgrade
Versão em desenvolvimento
Aqui você vai ter as atualização (quase) diarias do rekonq e seu desenvolvimento
Adicione o ppa
sudo add-apt-repository ppa:yoann-laissus/rekonq-ppa
sudo apt-get update
sudo apt-get upgrade