Você precisa instalar o PackageKit-command-not-found package:
dnf install PackageKit-command-not-found
É bom verificar sua configuração /etc/PackageKit/CommandNotFound.conf para alguns detalhes (está bem documentado), mas a configuração padrão deve ser suficiente.