I've just been reading a little about making steel, and from the simple descriptions of the process it's easy to see how superstitions could form around the process.
Even in the narrow range of concentrations that make up steel, mixtures of carbon and iron can form into a number of different structures, or allotropes, with very different properties; understanding these is essential to making quality steel. At room temperature, the most stable form of iron is the body-centered cubic structure ferrite or α-iron, a fairly soft metallic material that can dissolve only a small concentration of carbon (no more than 0.021 wt% at 910 °C). Above 910 °C ferrite undergoes a phase transition from body-centered cubic to a face-centered cubic configuration, called austenite or γ-iron, which is similarly soft and metallic but can dissolve considerably more carbon (as much as 2.04 wt% carbon at 1146 °C).
So if a primative iron-worker accidentally turns iron into steel, what's the most likely source for the dropped-in carbon? Organic materials, particularly small animals. When the product comes out harder and more resiliant than than expected from an iron tool, the difference could be attributed to supernatural properties of the "sacrificed" animal, the carbon donor.
Clayton Cramer sent a link to a paper he wrote titled "What Caused the Iron Age?" in which he argues that the answer is a regional shortage of bronze.