Found here: http://www.camulos.com/fordham/shoes.htm
"Whenever a pub takes the name of the Three Horseshoes, it is an indicator that a blacksmith or farrier was not far away. Why three shoes and not four? Because the horse would stand on three when he was being shod."
H'mmm.......that theory may be right, but I'm inclined to think it has more of a superstitious origin. The horseshoe is obviously regarded as a lucky symbol (now why that should be is probably material for another question!) and the number 3 (along with 7) was thought to have mystic powers and used in incantations and spells for that reason. Same reasoning applies to pubs called The 7 Stars.