Assumption: Exchange 5.5
1. Add a MX record in the DNS for the new domain. Point it to the existing IP Address. (May need to talk with your ISP abou this. If the domain does not exist in the DNS, they will need to create a new zone for it along with the MX record)
2. Add the new address as a secondary proxy address (see Technet for various artciles for how to's & troubleshooting, search by secondary proxy ) you can change the default for everyone via the Exchange Admin program. Configuration Container, Site Addressing object, site addressing tab - you can change the default SMTP address for all accounts in the site here.
3. Make sure to add the new domain entry to your IMC/IMS Routing table as a INBOUND domain, otherwise the system may reject it. Exchange Admin, Configuration Container, Connections.
Good luck
Rick