Apple - iPhone 4S - Locate your missing iPhone with Find My iPhone - http://www.apple.com/iphone/built-in-apps/find-my-iphone.html and: iCloud: Find My iPhone overview - http://support.apple.com/kb/PH2696
The following conditions ALL have to be met:
1) You have the "Find My" activated BEFORE you lose the device.
2) The device is turned on.
3) The device is able to connect to a registered wifi connection (iPad, iPhone, iPod Touch) or data network (iPhone, iPad).
4) The device was not restored by a finder of the device (if it was really stolen then the thief has probably restored it).
If you have activated the "Find My" feature, go to https://www.icloud.com or use the Find My iPhone app - http://itunes.apple.com/us/app/find-my-iphone/id376101648?mt=8
Setting up iCloud (requires iOS5) - http://www.apple.com/icloud/setup/ios.html - includes activating the 'Find My' feature.
Frankly in the case of a stolen phone this almost never works. Report it to the police. Change passwords on accounts. Tell your carrier to stop service. Go shopping for a new phone.
Kappy's missing idevice recommendations 09/2012 - https://discussions.apple.com/message/19569712
You can issue a lost mode (remote lock) or wipe command, but it will not be executed until the phone is turned on and has a connection to the internet. Nothing will happen, and you can't locate it until it's online again. (And if you erase it, you won't be able to locate it again. You only do this when you're fairly sure it won't be found anyway.) Here's a help article on Find My iPhone: http://help.apple.com/icloud/#mmfc0f0165.
So, my understanding is that if you don't upgrade to an unlimited data plan for an internet connection and are offline, or the phone is turned off due to the battery running down when trying to find your phone, then it seems a lost cause (no pun intended). Backing up the phone on a regular basis would help ease matters for a replacement, yet still, you've lost a phone. Not to be cynical regarding this post.