You go to
https://www.google.com/a/
Just sign up, tell them your URL, what your site is for and how many e-mail accounts you want. I told them 10 but they gave me 25. Then they tell you what to change the MX record to. You set up an admin account on google apps which allows you to create email accounts for other users in the format of
name@mydomain.com.
I had some problems yesterday though because the freehostia nameserver was down for an hour or 2 so I coundn't recieve any e-mail so I'm looking at trying to find somewhere that will manage the DNS that have a more reliable server.