How do I remove the "did you mean..." feature in the shell?

sudo apt-get remove command-not-found
sudo mv /usr/share/command-not-found /usr/share/command-not-found.bak

You need to restart your shell for the change to take affect.

sudo apt-get remove command-not-found command-not-found-data

Contrary to the other answer, you should not manually move things around under /usr unless you're trying to defenestrate your package manager.

The other answers here both assume root, and that you want to remove it globally for the system. If you just want to disable this for a single user (eg, your own account), you can simply do:

unset command_not_found_handle

either on the command line for the current shell, or in their .bashrc

The feature is typically enabled globally by defining command_not_found_handle in /etc/bash.bashrc, so could also be disabled there by default, while still leaving the package available for a power user to define the function and enable the feature in their own account.