Start with a simple mail script on a blank page like:
<?php
$to = 'nobody@example.com';
$subject = 'the subject';
$message = 'hello';
$headers = 'From: webmaster@example.com' . "\r\n" .
'Reply-To: webmaster@example.com' . "\r\n" .
'X-Mailer: PHP/' . phpversion();
mail($to, $subject, $message, $headers);
?>
If that doesn't work, then no emails from any php page will work. From there it is a server and SMTP configuration issue that I'm really not an expert at.
Just because you have a mail service running doesn't mean you have an SMTP server set up to allow relay from a web page.
You can read about the smtp settings that need to be configured in your php.ini file here: http://www.php.net/manual/en/mail.configuration.php#ini.smtp
If you're running Debian and variants thereof (*buntu, etc.), you can install a mail server by running sudo tasksel install mail-server, which should set you up with basic email capabilities.
You can test this by running in command line echo 'body' | sendmail recipient@example.net