copenhagen and a few other cities in denmark have a similar concept and it works really well. it helps that already a big majority of the population bikes to work and in town, plus denmark is very flat. there are a number of bike stands in the city, and you put in a 20 kr coin to rent the bike and get the money back when you return it. just like a shopping cart at a grocery store. the bike are simple, fixed gear bikes, but also have racks for your stuff. i have no idea if they are even stolen, but i dont imagine it. there are much better bikes around to steal.
also, every bike sold in denmark come equipped with a lock. its a small pin that engages at the back tire through the spokes and is attached to the frame. it basically just makes it impossible to move the back tire. most often, these locks are the only thing used, (no locking to a post), and while there is theft, its amazing how much the socially conscious aspect of the society alone just seems to keep theft at bay.
heres some other public bike systems-
http://www.springwise.com/transportation/city_bike_schemes/
R