It is effective against certain kinds of bike theft, particularly if you already lock up your bike effectively every single time (which is a good assumption if you're willing to go through the trouble to uglify it). Many people swear by it. For example, LDS missionaries in Taiwan repaint their new bikes poorly as a matter of tradition.
As Daniel already pointed out, there are several kinds of bike thieves. The US Deparment of Justice COPS report on bike theft in 2008 lists the following kinds of bike thieves:
- Joyrides: These thieves steal a bike for convenience or for pleasure, with no intention to resell it.
- Quick cash: These thieves are opportunist, looking for a quick buck to be made off of theft
- Planned theft: These are usually experienced thieves or experienced bikers who see a bike and steal it despite obstacles
To the first and second kind of thief, appearance is only a minor concern. To the third appearance is a major concern. The amount of each type of thief really depends on the area. In some areas very few are joyriders, whereas, in other areas mentioned in the report, up to 80% of the reported stolen bikes were abandoned and later recovered. Your risk for each type of thief also depends on where, when, and how you lock up your bike.
As these interviews with bike thieves point out, most bike theft of the first two kinds happens primarily because the bike is inadequately locked, not because of appearance, although appearance may deter these thieves regardless. Thieves often sell stolen bikes for dirt cheap, down to $100 or less, so to them it doesn't matter much if it looks like a beater bike or a racing bike. For example, my brother had his $80 old Walmart bike stolen when he left it in an apartment bike rack overnight with just a cable lock. The interviews even mention that bikes over $1000 are sometimes too risky for low-level thieves to steal.
All of this may explain why this study found that cheap bikes, including used cheap bikes, are among the most frequently stolen (see the picture below). The study also found that used bikes under $150 dollars are stolen many times more frequently than new bikes in the same price range. However, this raw data has some complexities, like how cheap old bikes are several times more popular than new, expensive ones and how expensive-bike-owners are usually more thorough in their locking practices.
That being said, there is a difference between making a bike look worthless and making a bike look repulsive. Stickers and rust are repulsive, while a bad paint job and a milk crate on back are just cheap. Making your bike look unsellable at any price should be your goal, not to make it look like a cheap beater.
Somewhere like New York with more of the third kind of thefts, planned thefts by seasoned thieves, is going to be an area where appearance matters far more and how you lock it matters much less. The interviews with thieves that I mentioned earlier shows how professional thieves will be ordered to steal an expensive bike or a certain brand of bike, or will see one and case it, coming back at an opportune moment with power tools or whatever it takes. Against these kinds of theft, changing appearance is one of the only methods of prevention.