I'm assuming you'll be de-commissioning the present exhange server, so here goes;
1) Install new Exchange server in the same site as the old one. Such that both servers appear in the Exchange System Manager (ESM) under the Administrative Group at the end of the install.
2) Open up the Active Directory Users and Computers, right click on a User and select Exchange Tasks...then select Move Mailbox - You should see both the old and new exchange servers here, so click to move the mailbox, the amount of time for the move will depend on the size of the mailbox.
3) Repeat Step 2 for all other Users.
At this point, users will not notice anything if you have done everything rightly as above. E-mails should still be sent and received as usual.
Now, it's over to the task of moving the following roles normally held by the first exchange server in an administrative group;
1) System folders, such as those holding calendar free/busy information.
2) The Recipient Update Service (RUS).
3) The Routing Group Master role.
4) Any Exchange connectors that are homed on, or have an endpoint on, the server to be decommissioned.
Because of time, I will continue this post later on, please let me know when you have performed the steps above.