There are some good DNS tools and articles on this site:
http://dnsstuff.com
MX records are what tells the world where to deliver your email. Chances are that your www host is also hosting your public DNS, so they will have to do the MX record updates, or they may have a control panel that you can use to make your own updates.
To find out for sure, go to your domain registration and see what is listed for NAMESERVERS. Whoever owns the nameservers listed on your domain reg, is your DNS host, and that is where the MX record changes need to be made. To see your domain reg, one way is to use the WHOIS lookup tool on the above site; enter your domain name to see the registration info (the tool may just link you to your registrar WHOIS and you may have to repeat the lookup there).
In your case, a couple of days before your new circuit is in place, and you know the IP that will be assigned to your exchange server, I would create an A-record and backup MX record (higher preference number than the existing MX) for the new IP. This will prime DNS with that IP since DNS changes can take days to propogate, due to caching. Once the new circuit is live and tested, I would swap the priorities of your MX records. This should result in a seamless transition of your email delivery without a loss or delay of a single message. Since you're leaving the current circuit in place as a backup, then I would leave that IP as a backup MX (higher preference number), and in the event that you need to, fallback to that IP should be automatic.
Caution, if you are not sure what you're doing with your public DNS, STOP! and find out for sure before you make a change. Errors in your public DNS can take down services, and fixing errors can sometimes take a day or days to propogate. I'm not trying to scare you, because it's not really that hard once you understand it, but this is the reality of the situation.
Hope this is helpful.
--C