Existem duas maneiras de fazer isso:
host ~ # apt-file update
host ~ # apt-file search nslookup
dnsutils: /usr/bin/nslookup
dnsutils: /usr/share/man/man1/nslookup.1.gz
gajim: /usr/share/gajim/src/common/nslookup.py
kaptain: /usr/share/kaptain/nslookup.kaptn
kvirc2-data: /usr/share/kvirc2/help/en/nslookup.kvihelp
libgnet2.0-0: /usr/share/doc/libgnet2.0-0/examples/dnslookup.c.gz
manpages-ja: /usr/share/man/ja/man8/nslookup.8.gz
procmail-lib: /usr/share/procmail-lib/pm-janslookup.rc
rbot: /usr/share/rbot/plugins/nslookup.rb
scrollz: /usr/share/scrollz/help/nslookup
zsh: /usr/share/zsh/4.3.4/functions/Completion/Unix/_nslookup
zsh: /usr/share/zsh/4.3.4/functions/Misc/nslookup
zsh-beta: /usr/share/zsh-beta/functions/Completion/Unix/_nslookup
zsh-beta: /usr/share/zsh-beta/functions/Misc/nslookup
e ...
host ~ # apt-cache search nslookup
host - utility for querying DNS servers
dnsutils - Clients provided with BIND