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".