Welcome to the forums,
Yup, and you probably won't have to make mail.mynewdaomain.us, the DNS records would just be:
mynewdomain.us mx = mail.mynewdomain.us
mail.mynewdomain.us a = server ip
Then you can make aliases on the new domain for your current accounts if you want users to send from both or something.
Move users to the new domain (simple drop down on the first page of their account settings)
-You could move them to the new domain, then put aliases on the old domain so they can receive mail at their old addresses.
allowing for some time for everyone to notify the domain name changes.
-Staying on the old domain, change the canonical address on everyone to that of the new domain, so when they send an email the from field will contain their new address.
If your moving them, do them all at once, so they continue to show up in the gal, or set the gal level to ROOT instead of DOMAIN.
If you plan on eventually removing the old 2 domains & changing your servername, make a backup before you do: ZmSetServerName - ZimbraWiki
zmprov mcf zimbraGalInternalSearchBase ROOT