If you try to execute a program that is not installed you will get a message
The program 'x' is currently not installed. You can install it by typing:
sudo apt-get install x
and instead of offering you to install the program for you, you have to type the actual command. How can this behavior be changed?
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.
