For bash, its behavior is governed by the shell function command_not_found_handle (See man bash, under COMMAND EXECUTION).
To see what behavior is defined by that function, you can issue:
declare -p -f command_not_found_handle
You can change which program is used by redefining the command_not_found_handle function.
In Ubuntu 14.04 LTS, it seems the default behavior is defined directly in /etc/bash.bashrc:
# if the command-not-found package is installed, use it
if [ -x /usr/lib/command-not-found -o -x /usr/share/command-not-found/command-not-found ]; then
function command_not_found_handle {
# check because c-n-f could've been removed in the meantime
if [ -x /usr/lib/command-not-found ]; then
/usr/lib/command-not-found -- "$1"
return $?
elif [ -x /usr/share/command-not-found/command-not-found ]; then
/usr/share/command-not-found/command-not-found -- "$1"
return $?
else
printf "%s: command not found\n" "$1" >&2
return 127
fi
}
fi