The easy way: most hosts (unless you're moving to shared, bleah) will migrate it for you, it's just good business, often for free.
Manually: Most of this is really easy with today's CP's. You just log in to the **new** server CP before it's live and create the accounts. Nothing will be collected in these new accounts until the DNS is pointed at it.
The one thing you'll have to do (and is usually the most difficult part!) is collect all the email login passwords from your users so you can do this - hard because, no one remembers where they put that stuff. I just click the button with the letter icon and everything just "works." :-)
If you can't collect the passwords, then when you switch over, you'll have to reconfigure all the users' mail clients with the new passwords - that is, Outlook will not be able to connect to your new mail server until you feed it the right password. Funny how the human element is always the most difficult. OK it's not funny, but anyway . . .
When the DNS re-points to the new server, it takes the mail with it - however - there are some instances where some email goes to the old box, some to the new box, while the WWW name servers populate. For example, if some customer is connecting to "you" from Canada and you're in Australia, their nearest DNS server may not "get" the update until later, so mail they send to you will be sent to the "old" server. This used to be at least a 72 hour period, but it's generally not more than 12-24 these days, sometimes sooner.
So before "switching over," work with your host and learn how to access the "old host" by IP address. That is, if you can reach your mail via the web interface at mail.example.com (or whatever the URL is,) figure out how to reach it by ip, like 123.456.78.68/mail-program-name. (Webmail, Horde, whatever . . . )
That way, as the DNS propagates, you can check the old mailbox for a few days until full propagation. Generally speaking, I've only found a few emails in there when moving clients. It's not a big loss, usually.
edit: I forgot: another way around the mail switch over is to open a gmail (or other third party) account, and on switchover day forward all incoming mail on the old server to the gmail account(s). Then anything coming in goes right to gmail.