MX records and nameserver changes

[#1]

Hello all!
I'm in charge of a website for one of our clients. They host their site with plus.net which is lovely for them but appears to be a nightmare for us.
Firstly, the website is all PHP and since connecting to the CGI space is not as easy task (I'm guessing I have to be on plus.net broadband to do it?) at the moment I have it forwarding to another host.
It's not an ideal solution, however, so I'd like to change the nameservers. If I do this, the company's entire e-mail setup will need changing on the new server.
So, a combination of nameserver changes and MX records is probably what I need to do.
Where do I change the nameservers on the plus.net setup and what do I have to do with the MX records (and how? I'm a bit fuzzy when it comes to that!)
Many thanks to anyone who can help and apologies for sounding grumpy!
Andy

[#2]

I had never realy touched DNS Records very until recently.
They're not too scary just that you have to be patient for the DNS's to Update / Refresh.
I think, all you'll need is...
1. The IP/Hostname of the Mail Server for the Company.
2. What type of mail server it is.
Meaning is it:
POP3 (Usually Port: 110 TCP)
SMTP (Usually Port: 25 TCP)
The MX Record will have to look something along the lines of this on the PlusNet Member Center - Domain Settings:
Left Field = BLANK
TYPE = mx
Pri = 20
Right Field = mail.mycompany.com.
**IMPORTANT NOTICE** you need to have a leading '.' on the end of the Right Field for a Hostname or IP Address. 
Hope that's right ... Hope it all goes well too
Jim,