How can I tell which package an executable came from?

install apt-file

$ sudo apt-get install apt-file

update apt-file

$ sudo apt-file update

search the package a file belongs to

$ apt-file search filename

find path of executable

$ whereis rename
rename: /usr/bin/rename.ul /usr/bin/rename /usr/bin/X11/rename.ul /usr/bin/X11/rename     /usr/share/man/man1/rename.1.gz /usr/share/man/man2/rename.2.gz

search package

$ apt-file search /usr/bin/rename
ladr4-apps: /usr/bin/renamer
util-linux: /usr/bin/rename.ul

the package name is: util-linux

Turns out dpkg-query is good to get information about installed packages, and with the -S [pattern] option will search for packages with files corresponding to [pattern].

dpkg-query -S [filename-search-pattern]

As of 2018

apt search filename

works for recent Ubuntu and most Debian based distros.

Update May 2018: Apparently no longer working with Ubuntu 18.04.