I went to the apple store a few days ago because of a tech issue I had with my iphone 4s. They deleted everything and had me start with practically a new phone. When I plugged my phone into itunes today, it synced up with the last time I backed up and deleted all NEW photos I took since I went to the apple store and all new messages. Is there a way I can retrieve these messages and photos?
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.
If the photos are deleted from your iPhone, try some data recovery program. Just google then you will get them. Some are free.
By the way, don't save any data file on your file before retrieving your photos back.