I'm new to this whole hosting thing, my situation is the following. If my domain is being hosted at a company and my email is with another company. What do I need to give to the hosting company so that the other company is able to host my mail? I was thinking I need to get the MX records so that the hosting company can add them at there site? Is this correct?
You indeed need to configure your DNS records in order to have MX records point at your other server. Typical DNS config in this instance, supposing 203.0.113.3 is the webserver and 203.0.113.4 is the mail server:
example.com. IN A 203.0.113.3 www.example.com. IN A 203.0.113.3 mx.example.com. IN A 203.0.113.4 example.com. IN MX 10 mx.example.com.
I'm guessing your web server provider also provides DNS servers, so you must have some kind of web app to configure this. If not, you should look into DNS servers (Bind, PowerDNS).
Pretty much. Ask your mail host what the addresses for their mail servers are, and give that to your hosting company so they can change the MX records on your domain to those servers.
This is assuming that they are hosting DNS, and it's not being done through someone else such as the registrar where you bought the domain