Q:

How does Ubuntu knows that a program is contained in a certain package?

Using in Ubuntu (on command line) a program, e.g. "sar" which is not installed, it tells me which package contains this program.
user@comp ~$ sar
the program 'sar' can be found in the following packages
* sysstat
* atsar
Try: sudo apt-get install <selected package>

How does this work?

A:

The bash shell uses a special user-defined function called command_not_found_handle(). To see the description of how bash uses this function, type info bash and search for "not found" -- or read it online here.
On Ubuntu 14.04.3 LTS, the function is defined in /etc/bash.bashrc, which is installed as part of the bash package. The function invokes either /usr/lib/command-not-found or /usr/share/command-not-found/command-not-found.
If you prefer not to have this behavior, you can use this command:
unset command_not_found_handle

to remove the function definition.

