It was my bike being stolen that led me to this most excellent forum, so I am going to try and make a good thing of a bad and relate my steps to recover my recently-stolen Jamis. If the unthinkable happens to you, here's what you do:

Treat it like a crime scene, because it is. I'm sure everyone here has seen at least one episode of Law and Order or CSI, so you'll know what to do. Look for anything different in the area, such as signs of forced entry. I noted that my back gate was closed but unlatched, which I assume was thanks to the thief. Granted, the theft of your bike will probably not demand a team of detectives complete with crime lab, but it can't hurt.

Call the police. If the bike has been stolen very recently, call 911. If it's been gone for at least a few hours, call 311 (The city of Minneapolis has a very useful public service line) and they can direct you to the proper authorities. You can make a report over the phone. It's my understanding that officers will generally not physically come to the scene for this kind of crime. If you prefer, you can file a report online. I opted to report this online, and it's fairly painless. You can describe your bike in detail and give a fairly thorough account of the crime. You will receive an e-mail with a case number if you elect to do so.
I have not been contacted by the police, but having a case number on file will greatly assist you in tracking down your bike in some later tips.

Call around. If you're anything like me, your bike has some quirks that you find endearing but others may find annoying. If anything needs repairs beyond what your average bicycle thief can manage, it's possible that they will bring it in for repairs, or perhaps to sell the bicycle or components. Call area bike and pawn shops. Penn Cycle, which has locations throughout the metro, has an e-mail list that goes out to all their locations - when I called the guy offered to send out a description.
Your chances here are actually pretty slim. Most thieves don't really care about the condition the bike is in, and due to their high rate of theft bikes don't really have a good pawn value. By state law, all pawn shops have to compare their incoming goods to the list of stolen property on a daily basis - another reason to report your theft. You can request a search of this database by calling 612-673-2932 during business hours.

Get the word out. I'll be honest - your chances of recovering the bike aren't that great. Right or wrong, the cops tend to put a fairly low priority on tracking down bikes. You may have to take the law into your own hands and dispense some vigilante justice - by which I mean post notices to the Cragislist Lost and Found and/or Bike boards. Post to the Stolen Bikes forum here, of course. Make sure you post the area that it was stolen in so folks can keep an eye out. Bikes are often stolen and dumped, and most people will take note of a bike lying around unlocked where it shouldn't be.

Check with the city. If you're like me and lost the serial number, or never took it down in the first place (It's generally under the bottom bracket) then the chances of the police recognizing a given bike as yours are significantly reduced. The city picks up abandoned bikes routinely and stores most of them in a warehouse at 60th and Harriet, one block off of Lyndale. Call this warehouse at (612) 673-2932 Monday through Saturday, 8:00 a.m. to 9:00 p.m to arrange a visit. (By appointment only) To reclaim your bike, you will need to prove ownership. Bring a receipt, serial number, or a picture of you with the bike to reclaim it.

Hit the auctions. Minneapolis routinely auctions off recovered bikes in their possession for thirty or more days. You can see a schedule of these auctions here. These auctions take place at the evidence warehouse mentioned above. You need to provide the same information as above to reclaim your bike, or you can buy it back via the auction. (If you lack evidence proving ownership) Most of these bikes go very cheap, so paying $50 to get yours back is probably worth it.

That's all I've got! Please add your own advice for recovering a stolen bike.

Nice list of tips - out of curiosity, did any of these work for you?

Sadly no.

I once recovered one of my stolen bikes by doing detective work. It was stolen from in front of an arcade which had a dirt path leading out of a parking lot. My friend's bike was also stolen so we were walking around and saw sets of tire tracks that matched the tires we had on our bikes. From there we followed them up to an asphalt road, where they disappeared, but we picked them up on the other side. we saw that they turned ont another road leading to an apartment complex, so we went down the road, all the while searching for more tire tracks. We picked up the trail again leading to a wooded area, and finally, hidden in a bunch of trees and brush were our bikes.

Yeah, we got lucky, but it wasn't uncommon back then for kids or people to ditch bikes and come back for them later.