You probably need to change the configuration under
Admin > Email Settings or maybe you can't connect to your email server (connection down, blocked by firewall, etc.).
Look at the record for the notification, which is found in the APP_MESSAGE table in the database to make sure that it is sending to a valid email address and coming from a valid account.
Remember that the email's FROM line should be the same as the email account that you configured under
Admin > Email Settings. For example, if you configured to send email from the account of
mary@example.com, but you are trying to send it from the account of
todd@example.com, then most email servers will reject the email as spam.