Ask to install program after "The program 'x' is currently not installed"
The package that is responsible for this behavior is the command-not-found 
package, and it already includes the desired behavior although it is disabled by default. You can enable it by adding the following line to your ~/.bashrc
export COMMAND_NOT_FOUND_INSTALL_PROMPT=1
Now the behavior is changed to
The program 'x' is currently not installed. You can install it by typing:
sudo apt-get install x
Do you want to install it? (N/y)
Note:
If you get a message about python crashing (specifically AttributeError: 'str' object has no attribute 'decode') this is bug 1073919. A fix is already available for Raring and Saucy. Alternatively (advanced users only), you can change the file /usr/lib/python3/dist-packages/CommandNotFound/CommandNotFound.py, see the diff attached to the bugreport for the lines that need to be changed.
Edit: The fix is now released in version 0.3ubuntu7.1 in Raring (SRU) and for 0.3ubuntu8 in Saucy.
My solution is an hybrid between security and comfortability:
auto-apt checks the file access of programs running within its environments, and if a program tries to access a file known to belong in an uninstalled package, auto-apt will install that package using apt-get. This feature requires apt and sudo to work. It also provides simple database to search which package contains a requested file.
It's a terminal-emulator where you enter a environment where each file access is verified before hand by auto-apt and if it not exist it search in the database (a la apt-file) and download and install the desired package, then allows the program to continue. You should execute it as root:
sudo auto-apt
This is useful in cases where you are building a package and isn't in the mood to be in front of the screen looking for each configure error for missing headers, etc.
This also can be used as apt-get + apt-file replacement where you can install programs just telling the command to execute it.
You must understand that you should not leave it opened when your system isn't looked, since it's almost as if you were using the root user.
Man page: http://derpi.tuwien.ac.at/cgi-bin/man/man2html?1+auto-apt