First, from the device's main screen, go to: Settings > Mail, Contacts, Calendar > Add Account > Microsoft Exchange.

Under account info, in the Email address box, enter your hosted Exchange email address, then fill in the Domain, Username and Password fields with the information you have been provided. Tap on the Next button at the top of the screen.

NOTE: Your device may fail at this point, stating "Unable to Verify certificate." If this is the case, just tap Accept.
A box labelled Server will now appear. Enter in the Server details provided to you, then tap on the Next button at the top of the screen.

The device will then verify the server saying "Account has been verified."
A new screen will appear asking you to "Select info to synchronize using Exchange." It will display Mail, Contacts and Calendars. Turn the features ON if you desire to have them synchronized with your Exchange account. Once satisfied, select the Save button.
NOTE: If you would like to keep the existing contacts on your phone, click Keep on iPhone. (The ability to keep both local and exchange details only appears to be available on phones with the iPhone 3.0.x software.) If your phone doesn't have a "Keep on My iPhone" button, you may want to update your phone via iTunes.)
If you choose DELETE at this step, the contacts on your iPhone will be LOST.

You will then be taken back to the default Mail, Contacts and Calendar screen. You can adjust the mail settings preferences here as you wish.

By default the iPhone will only sync the last 3 days of mail. To sync older messages, Please do the following:
Go to : Settings - Mail, Contacts, Calendar.
Tap on the Exchange account. Tap on Mail days to sync and select from No Limit (which will sync all messages) to 1 Month.

Congratulations! Your new account has now been setup!