How do I find the package that provides a file?

Simple enough question: is there some shell command (or GUI method) I can use that, given the path to a file on my system, tells me what package put it there? Assuming the file did in fact come from a package, that is.

Bonus question: what if it's a file that isn't installed on my system? Is there, say, a website that will let me look up a file and see what packages, if any, provide it?

You can use dpkg command to find out which installed package owns a file:

From man dpkg:

-S, --search filename-search-pattern...
                  Search for a filename from installed packages.

Example:

$ dpkg -S /bin/ls
coreutils: /bin/ls

You can either search with a full path or with just the filename.

If you wish to search for files not yet installed on your computer, you can use the Ubuntu Packages Search