Restoring from new means NOT selecting the iTunes/iCloud backup after restoring. Any data stored directly on the phone will be lost. Now it depends on how the phone has been set up, but usually bookmarks and contacts are kept synced with the person's iCloud account. To make sure this is the case, go into settings > iCloud and check and see that Contacts and Safari are turned on. You can also turn on other things to keep them synced as well. Data that has been synced to iCloud... with the exception of what is stored in the phone's backup file... will automatically by put back on the phone after restoring as new.
Other apps will sometimes have the ability to backup and/or sync their data with iCloud or another online service such as dropbox, or alternatively may be able to download their data to a computer through iTunes.