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

Auto installing would be a bad idea. If you want to save some typing you can use

sudo apt-get install !!

where !! will be replaced by the last command from history. You probably could make this an alias as well, but I don't know how to add !! without evaluating it.

There are some caveats though, as mentioned by @eliah-kagan and @gertvdijk in the comments. Some programs doesn't have the same package name as the binary you would execute. Also, when passing arguments to the binary, this could result in some unexpected results.

There are a few methods for quickly installing the suggested package:

• Add export COMMAND_NOT_FOUND_INSTALL_PROMPT=1 to somewhere like ~/.bashrc

  this is the "coolest" way, although obviously not quite as safe, but probably 90% of the time will elicit an internal "Thanks, that's exactly what I wanted you to do!" response.

  (One personal drawback of this method is that I seem to find the answer difficult to remember/search for, so I tend not to have used it much so far.)

• If you are using the default Terminal, you can quickly select the line and middle-click to paste it directly into the command line. (Other terminals or SSH apps may have different methods.)

  In practice, I tend to find this quick enough, and slightly harder to do "accidentally", and without requiring any prior setup, that I tend to do that instead.

• There is something to be said, though - if you can (or want to learn to) type quickly - for typing out sudo apt install packagename directly.

  It helps you exercise your muscle memory, and also means that you have to read and type the package name, meaning you're likely to remember it more easily in future. It's also slightly easier in more recent Ubuntu versions, because apt works in place of apt-get.