If you use ZSH and want the well known “command not found” feature, you simply have to add source /etc/zsh_command_not_found in your ~/.zshrc. If it’s not installed at all: aptitude install command-not-found.

If you don’t know what “command not found” does, here is an example:

% play
The program 'play' is currently not installed. You can install it by typing:
sudo apt-get install sox
zsh: command not found: play

It tells you in which package you’ll find a specific command when you type it and it’s not installed. How great is that?