One of the features of Ubuntu that I really like is the one that suggests packages to install if you try to run a program that isn't installed, like this:
$ nmap
The program 'nmap' is currently not installed. You can install it by typing:
sudo apt-get install nmap
Is that a fancy feature of Bash? An extra daemon that hides in the background? How does it do that?
command-not-found is the package you are looking for.
Just as an addition to the previous answer:
To switch this off for your own account (without deinstalling the whole package and so disabling this for ALL users), you may just add the following line to your own ~/.bashrc:
This reverts to the default bevaviour of bash (see /etc/bash.bashrc for the definition of the function command_not_found_handle: it calls command-not-found if it is installed, otherwise it prints the default "command not found" error message).