Alright, let me start off by saying that I know there are better and more professional solutions for sending email on web servers. But sometimes you just want to use PHP's mail() function to get it done quickly and simply.
Here are the steps I took to get sendmail working on my Ubuntu server.
Sendmail might already be installed, but just in case, enter this into the server terminal:
sudo apt-get install sendmail
Enter the following command into the terminal and type "Y" for each question it asks:
Time to edit your server's hosts file, access it by entering the following command into the terminal:
sudo vim /etc/hosts
Add the following line to the top of the file and save it:
127.0.0.1 localhost localhost.localdomain your_domain_name_here.com
Comment out any duplicate lines that already existed.
Let's restart your server just for good measure. At this point emails sent via PHP's
mail() function should be sending successfully and without much delay.
sudo service apache2 restart
I hope this solved the problem for you. I've followed this exact procedure on three different Ubuntu 14.04 LTS servers and it has worked for each one.
Send me a message and I'll get back to you within one business day.