You didn't specify so I will assume that you are running an SMTP server and an IMAP server/mailstore on the same machine.
Servers have hostnames not domains and are members of a zone; this is a common confusion.
If you have a machine with a hostname examplemail.com that accepts mail for the zone examplemail.com you can indeed bring up a mail server on another machine called mail.exampleserver.com that accepts mail for that zone.
In order to do this you should first configure the new machine to accept mail for examplemail.com (and probably configure it to allow your users to send outbound mail through it, preferably using a polite encrypted SMTP-AUTH setup).
Once you're happy that the new server works, you'll need to make DNS changes so that folks will use it. If you're concerned about caching, you might want to set the TTL for the zone down to an hour or even less before you start fiddling with DNS.
You should change the MX records for any zones that you want the new machine to handle to look like this:
examplemail.com. IN MX 10 mail.exampleserver.com.
If you want to avoid reconfiguring your users' clients, you'll also want to create a CNAME that points from the old to the new:
examplemail.com. IN CNAME mail.exampleserver.com.
Don't forget to consider reverse DNS. What should the reverse lookup for the IP address of the new machines look like? examplemail.com or mail.exampleserver.com?
Also, don't forget to modify your SPF records if you use them.
There's a lot more to migrating mail servers than this, especially if you're very sensitive to downtime and user visibility, but it's a start; hopefully you have things carefully in hand and have tested the 'restore' part of your backup process:)