Primeiro, verifique se sua impressora já está conectada e ligada.
Eu instalei a partir da linha de comando usando:
$ sudo apt-get install python-qt4 hplip-gui
como PJ Singh sugeriu, então da linha de comando eu corri:
$ hp-setup
e clicou na GUI para configurar tudo. O programa detectou automaticamente minha impressora e uma página de teste foi impressa com sucesso.