I'm assuming this is standalone Exchange and not Small Biz Server. In your Exchange Server, look at your recipient policies (ESM/Recipients/Recipient Policies), this is where you'll make the change.
Depending on how your policy is set up, you'll either have just the Default Policy, or you'll have the Default and 1 or more custom policies. Find the policy that has your existing domain in it and ADD the new domain to the same policy. When you add the new domain, check the box that says "This Exchange Organization is responsible ..."
Once you have the new email domain added (and don't make it the default email domain until you test it), you can rebuild RUS (ESM/Recipients/Recipient Update service). Give RUS some time to complete, minutes to hours depending on the size of your organization, you can go back to the recipient policy and 'Apply this Policy now ...' and shortly, everyone's email addresses will be updated with the new domain automatically. This means that mail sent to user@oldcompanyemail.com and user@newcompanyemail.com will end up in the SAME MAILBOX.
Once the new domain is tested and you want to make the new email domain name official, go back into the Recipient Policy and make the new email domain the default, Rebuild RUS, and re-apply the policy. Users will still receive email addressed to both domains, but their email address being advertised in their OUTBOUND email will be the new email domain.
Exchange doesn't care, You can leave it set with the multiple email domains indefinitely, or you can remove the old domain at some point in the future, by removing the old domain from the Policy, rebuild RUS, re-apply the Policy.
This one's gotta deserve the Thumbs Up button :-)