Your mail settings are most likely incorrect in the admin under the Mail Server setup configuration.
You can test if the system is setup by sending test messages from the admin. The admin send process is the same as the store sending process.
If the test message goes through but you are still receiving an error on the website, make sure that the specific message type (i.e. Customer Registration Confirmation, Order Confirmation, Tell-A-Friend, etc) is set to Active and contains a valid "from" address in the profile.
If you need help diagnosing email sending issues or setting up your specific install’s mail server settings, please contact support for assistance.