apt-cache search python zmq
retorna
python-zmq - Python bindings for 0MQ library
python-zmq-dbg - Python bindings for 0MQ library - debugging files
É isso que você está procurando? Então
apt-get install python-zmq
deve funcionar.
Para pesquisas futuras:
Os módulos Python no Debian e no Ubuntu são frequentemente chamados de forma diferente:
python-<module name> em que <module name > geralmente não contém "py" ou "python".