when you sync with itunes, in the info tab check "contacts" and if on a mac it stores in Address Book, and if on windows you tell it where to sync.
then, if you want to restore your phone and set it up as new (instead of from backup) you just check that box again and point it to the same place.