0On Ubuntu and Friends
Suppose you know that you need a particular file, e.g. /usr/bin/xpdf, in order to run a desired command or compile some software. You can find out which package provides that command with the apt-file package, e.g.
sudo apt-file update: updates database
apt-file /usr/lib/libRmath.so: reports the name of the package that provides /usr/lib/libRmath.so
0On Fedora and Friends
yum provides /usr/lib/libRmath.so