Note: I'm assuming that you're already running Traveler and are able to get your mail and calendar.
Enabling Contacts Synchronisation
In IBM Notes, Select File, then Preferences.
Click on Contacts
Make sure that this is turned on;
[x] Enable "Synchronise Contacts " on the Replication and Sync Tab
While you're in here, make sure that in the Recent Contacts section you have selected;
(o) Do not add any names
This bit isn't critical to the procedure but it's caused us no end of grief. It's fine if you don't have lots of outside contacts in a giant corporate address book but it's painful if you do.
On the top Left of Notes,
Click Open, then Replication and Sync
Make sure that [x] Synchronise Contacts is Enabled.
Setting a Replication Schedule
Click Schedule and then Set Replicaton/Sync Schedule.
Ensure that the Normal Priority is on and at least set to run every 60 minutes on at least business days.
That's it, give it a few minutes (probably less than 5) and you'll have a phone full of contacts. From now on, you can update your contacts on your phone or in your person address book and they'll synch.
Special Note: Don't forget that if you remove and reinstall (or upgrade) your Notes client, you'll probably need to redo these steps or the synch will stop working.