How do I retrieve my photos/messages?
There is no way, unless it was backed up somehow. If iCloud was enabled, and backed up recently, you will be able to restore it from an iCloud backup. Here is an article detailing the restore of an iCloud backup http://support.apple.com/kb/HT4859 .

When you restore a phone, or start over, there will be three options on the initial wizard (iOS 5 only - which is on the 4S). The three options are Restore from iCloud backup, Restore from iTunes backup, as well as Setup as new iPhone. As a result, the only real restores you can do is iCloud (which is extremely easy), as well as iTunes (which is very similar, only you must connect to your computer). iCloud automatically backs up every night if (1) your phone is connected to wifi (2) your phone is locked and (3) your phone is locked, therefore it often can be more recent then iTunes.