Please check if your server sends any email messages at all. Go to Global configuration to see Mailing parameters. Please check if Contact Us form sends any emails.
By default, Joomla is set to send emails through PHPMail, but it should be installed on your server. You can use SMTP or Sendmail. Please try different parameters and contact hosting provider if you need furter help and information.