I did that earlier this year.
First I set up a non-crucial domain on the new host. Setting up an email service was unfamiliar territory, so it took me a while to get it right. But eventually, I had it all figured out and I was able to send and receive email for firstname.lastname@example.org
Once that was working, I configured the "real" domain on the new host... basically mimicking the same configuration I used for the dummy one. I still hadn't switched the DNS.
I could tell it was working by doing a few experiments with telnet on the new host - I relied heavily on www tutorials for that part. Eventually I was pretty confident that I hadn't screwed anything up.
To grab all my mail off the old server, I connected to it with POP instead of IMAP, and waited as all the email showed up in my mail client. That took a while. I did a few test sends & receives to make sure I'd really got everything downloaded locally.
For a larger organization I'm sure that wouldn't be sufficient. But here I was only concerned about me (I have no staff & employees with their own mail)
Eventually - and this was after I'd also configured the web server on the new host too - I took a deep breath and changed the DNS. I will admit it felt like a Hail Mary. Was I lucky, or was I prepared? Either way, everything worked fine... All the web traffic started flowing through the new host, and I was getting email from it too. Phew!~
Did I lose any mail during the DNS transition? Actually I have no idea. I don't think I did. The old host was still "hooked up" and running, but it stopped getting incoming mail. Maybe there were some in-between moments where mail was going to both.
That's my story. I bet an experienced IT Admin would roll their eyes and tell me everything I did wrong. Like you I'm interested in knowing the *right way* to do this.