No Ubuntu, está em dnsutils . É o mesmo no Debian.
Instale-o com:
apt-get install -y dnsutils
apt-file permite pesquisar arquivos em pacotes, mesmo que não estejam instalados.
Eu tentei instalar o dig no Debian, mas o utilitário apt-get não parece saber o que é.
É parte de um conjunto maior de pacotes? Onde posso encontrar isso?