Lost iPhone, what action to take?
No need to suppose, that just happend to me (somewhat).

Preventive measures

As of today, suppose you have an iPhone 4, iPad or new iPod Touch running iOS 4 and you had previously activated the free MobileMe "lost my iphone". Then you're in the best situation of all. Suppose you don't have any of the new iDevices, but still are on iOS 4 and want to activate it for free. There are ways around that, for now, if you can borrow a new iDevice.

All you got to do in that situation is go to the website and get the measures of your choice. It will depend on how you lost the phone. If you know it was stolen, lock it first; don't display any message and track it down. Wiping is always the last resource, unless you're paranoid about leaking data. Be aware you will lose the ability to use everything else - it will reset to factory defaults. If you just forgot it somewhere, send an SMS first - maybe you'll get lucky.

There are also many tools on Cydia store to locate an iPhone - lost or not. I personally use and enjoy Longitude. It's, by far, the cheapest one and does the very basic stuff - send location to Google Latitude within a time interval you set. Enough for me.

But all that will only work for a couple of days at most. After all, iPhone battery doesn't last too long with 3G enabled. And, of course, only if it's turned on.

Taken by surprise methods

You may have not prepared yourself for the worst. Or you may have done it, but found out about your lost iPhone too late and it's now turned off, battery dead or being re-sold in the black market after being wiped already.

There are 2 additional steps to do. Both include reporting it lost or stolen to the carrier. If you just ask for a phone lock, you can save yourself from a big bill made by someone ill intentioned calling to China. That's the SIM lock and it can be undone later at any time.

Now suppose you didn't have a passcode lock on the phone and have no MobileMe. Then all your data is available to the finder / thief of the iPhone. That can concern a lot of people.

There comes the last measure - disable the phone through the IMEI. On most phones you need to have written down the IMEI before it got lost. It may be on the manual, box or some place else. On iPhone, tho, that information is on iTunes and easy to find.

Make a police report on lost / stolen, get the IMEI, call the carrier and the phone should become useless. Supposedly, nobody will ever be able to use it as a phone again - not even you. My carrier promised me the phone doesn't even turn on anymore. While that's probably not true, at least your data will be supposedly wiped. (disclaimer: I'm still trying to verify all those suppositions)

If the thief wipes the phone (by reinstalling the iOS) you won't be able to track it through iCloud / find my phone / or any other tracking app, but the IMEI block is still worth doing. More and more carriers are starting to enforce the IMEI blocks on stolen phones unless the person with the phone goes back and argues to get it lifted. I don't know what would happen then, but I would suppose unless the person had a sales receipt, the carrier wouldn't serve that device after it being reported stolen.