mail can represent quite a couple of programs on a linux system. What you want behind it is either sendmail or postfix. I recommend the latter.
You can install it via your favorite package manager. Then you have to configure it, and once you have done that, you can send email like this:
echo "My message" | mail -s subject [email protected]
See the manual for more information.
As far as configuring postfix goes, there's plenty of articles on the internet on how to do it. Unless you're on a public server with a registered domain, you generally want to forward the email to a SMTP server that you can send email from.
For gmail, for example, follow http://rtcamp.com/tutorials/linux/ubuntu-postfix-gmail-smtp/ or any other similar tutorial.