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.