How can I configure zsh to let it explain to me where I can retrieve an executable instead of saying file not found?

The default zsh configuration for Debian (and probably Ubuntu) just doesn't include support for the command-not-found package per default.

In order to have the same functionality you just have to source /etc/zsh_command_not_found in your ~/.zshrc per default via:

[ -f /etc/zsh_command_not_found ] && . /etc/zsh_command_not_found

This should load and enable the command-not-found functionality in zsh.