Command Not Found -- Okay, Where Do I Find It?

Okay, Debian (and, therefore, Ubuntu) has more packages than anybody, so if I need a Linux command, it's out there somewhere. But where?

Someone's created a lovely hack that solves this problem. It comes on Ubuntu by default.

$ foo
bash: foo: command not found
$ kedit
The program 'kedit' is currently not installed. You can install it by typing:
sudo apt-get install kedit
bash: kedit: command not found

The details of how this works are in the bash man page -- look for command_not_found -- and there's a discussion here.

This won't solve all my problems, since commands are sometimes not called what I think.

$ flash
The program 'flash' is currently not installed. You can install it by typing:
sudo apt-get install kmd
bash: flash: command not found
$ apt-cache search kmd
kmd - Komodo Manchester Debugger

The package for Adobe's Flash player is called flashplugin-nonfree
But I guess I should be installing gnash anyway.