What is the differences between MX record and CNAME record?

[cache]

I am trying to offer some email service for my own domain through gmail free standard edition.
How do I set it up? Some previous discussion mentioned the MX Record.
However the gmail setup prompted me for the CNAME record.

What is differences between
(MX record and CNAME record)?

How can I set it up?

My second question is where do you change the MX record or CNAME record?
Are they changed at the registrar or at the hosting company?

Thanks.