In a lot of modern stories, iron is fairies' kryptonite. Their silver bullet. All the hero has to do is whip out a cast-iron skillet, and evil sprites cower.

It's often explained as iron having natural anti-magic qualities, or symbolizing the march of industrialization and the fading of magic. Or any other of a billion explanations.
​
For further confusion, it's not just iron. It's "cold" iron. The phrase can be baffling to modern readers, and for maximum confusion there actually is such a thing as cold-wrought iron. However, cold-wrought iron is newer than the phrase "cold iron," which in this case is poetic. "Cold steel" is the modern equivalent and simply means a weapon that to draws blood (Current Literature, 1891).

Where did this originate? It's just one of those folkways that can never be sourced to any one person, and always seems to have been "well, everyone knows it." However, you can trace it back through history to an xtent. 

In Robert Herrick's "Another charme for stables" (1648), the reader is told to hang up metal hooks and shears to protect their horses from being ridden at night by witches.

In 1691, Robert Kirk wrote that "The Tramontanes, to this day, put bread, the Bible, or a piece of iron, in womens bed" to prevent newborn children from being stolen by fairies; and "they commonly report, that all uncouth, unknown Wights are terrifyed by nothing earthly so much as by cold Iron."

So the phrase and the tradition date back at least to the 1600's. The iron seems to be more popular than the bread as a popular way to repel fairies. I guess it's just not as exciting to send your hero into battle wielding a baguette.

The superstition of leaving iron in the bed to prevent fairies kidnapping expectant mothers continued over the centuries. Thus, the way to protect children from being replaced by changelings was usually to leave open scissors, a knife, fire tongs, or a similar object near their cradle.

Around 1850, in Northern mythology by Benjamin Thorpe, a story is related where a smith sees a troll kidnapping a pregnant woman. Since the smith is working at his forge, he uses a piece of red-hot iron to frighten off the troll.
In other stories in the same volume, trolls and huldra seem to have no trouble with iron. And, like, most people don't want to be chased with red-hot iron. That's not just a magical creature thing.
However, there is also a mention of a Danish tradition that "On the eve of Maundy Thursday the country folks cast axes and iron wedges on the sown fields, and fasten steel on all their doors, that the witches may not injure them."

In the Ozarks, there were many traditions surrounding iron nails. They could be nailed into someone's footprint - either to hurt an enemy, or a witch. They could be used to prevent disease, or they could be driven into a doorframe, which was particularly effective in protecting (again) pregnant women from evil. These practices were recorded around 1947.

So these superstitious practices surrounding iron are surprisingly long-lived. Right into the 20th century! On the other hand, they also go back further than I originally realized.
In Natural History, Book XXXIV, Chapter 44, Pliny the Elder mentioned that iron was used both in medicine and in preventative magic.
"Iron is employed in medicine for other purposes besides that of making incisions. For if a circle is traced with iron, or a pointed weapon is carried three times round them, it will preserve both infant and adult from all noxious influences: if nails, too, that have been extracted from a tomb, are driven into the threshold of a door, they will prevent night-mare."
There is much more about iron and magnets besides this, but this quote alone establishes a history for iron as having magical protective properties.
And that was around 79 AD!

So at first, it was simply that iron could protect and heal people. Actually, some of the superstitions in Pliny - like iron having healing properties, or the idea of driving nails into a door - were still pretty current in the Ozarks almost 1900 years later.
It's easy to see how it could go from "iron protects from evil" to "iron protects from sickness, evil spirits, witches, and fairies" which were all kind of interchangeable at that point. Many of the superstitions center around vulnerable groups, like pregnant women and small infants.

A Victorian theory is that the first iron found was from meteorites, which would give it an otherworldly and sacred meaning as something that had fallen from the heavens. However, that's speculation.
Iron is a hard and durable metal with the possibility of becoming magnetized.  There are beliefs about it and evidence of it being used in amulets and charms for about as long as iron has existed. It was seen as pure or impure by different groups. There were quite a few superstitions surrounding blacksmiths, as well; blacksmiths having healing abilities or, in Scotland, being allowed to perform marriages; and there were gods who were smiths, like the Greek Hephaestus. 
There are more esoteric explanations, like iron being seen as the lifeforce of the earth, or associated with lifeforce because blood smells like iron.

There are superstitions associated with every substance known to humankind. There are some negative superstitions associated with iron, too. This one just happens to be the most well-known.

Further Reading

• Robert Means Lawrence. The Magic of the Horse-Shoe. 1898. Chapter 6, Iron as a Protective Charm.
• John Gregorson Campbell. Superstitions of the Highlands and Islands of Scotland.
• Edgar Thurston, C.I.E. Omens and Superstitions of Southern India.
• Steve Roud. The Penguin Guide to the Superstitions of Britain and Ireland.
• Cora Linn Daniels. Encyclopedia of Superstitions, Folklore, and the Occult Sciences, Volume 2.
• Randomdescent. Iron in Folklore.​

Fairy tales are obsessed with hunger. There’s Thumbling, Jonah, Red Riding Hood, and Zeus's siblings, all gulped up only to emerge unharmed one way or another. In many stories, In stories from all over the world, parents threaten their children that some boogeyman will gobble them up if they don't behave. 

In Hop o' my Thumb, the ogre hungers for the flesh of children. In Jack and the Beanstalk, the giant chants "I smell the blood of an Englishman . . . I'll grind his bones to break my bread." These man-eating giants hearken back to monsters such as Polyphemus in the Odyssey.  Hansel and Gretel's witch is the same character. ​The evil queen desires to eat Snow White's heart. In Perrault's Sleeping Beauty, the second half features the heroine's mother-in-law attempting to eat her and her children cooked with sauce piquante.

And on the other hand there are stories where people are tricked into eating human flesh, especially the flesh of their loved ones - as in The Juniper Tree and some older versions of Red Riding Hood. In the Vietnamese story of Tấm and Cám and the Greek myth of Philomela, it's the hero tricking the villain into cannibalism.

There's one theory that the frequently-digested Thumbling is a story related to how children process the concept of pregnancy and childbirth.
This motif of being eaten and escaping appears in other tales, like Red Riding Hood and The Seven Kids. 
Earlier theories suggested Red Riding Hood was a myth-like tale of rebirth, with the girl as the sun and the wolf as the night. That school of thought has now been largely discarded, and it's more popular to read it in sexual terms, perhaps as the devourer eating a lover in order to possess her completely. Hunger in fairytales is often a stand-in for sexual desires.

There are other factors behind the stories, though. I think it's partly ancestral fear, the fear of a bigger predator snatching you from your cave.

It could also be a way to face the taboo. In the 1997 article “Incest in Indo-European Folktales,” D.L. Ashliman points out that “many fairy tales owe their longevity to an ability to address tabooed subjects in a symbolic manner."
So, along with stories containing abuse or incest, there are stories like The Juniper Tree where people, even parental figures, turn to cannibalism.
Perhaps this is also where the heroes taking harsh revenge come from. In a story, you can dance the villain to death in red-hot iron shoes or send her hurtling down the street in a barrel lined with nails.

There are some beliefs that eating your enemy - usually in a ritualized ceremony - will give you his strength, courage or life force.
The Iroquois and Aztecs would do this with prisoners of war. The Sawi (Sawuy) people of New Guinea would give the victim's name, and thus his life force, to one of the villagers. 
In Tanzania and other areas of Africa, some superstitions hold that albinos are magical and their bodyparts can be used in talismans or potions. 
In Europe, human fat, flesh, blood and bones were consumed in medicines until around 1750. 
Consuming the life force would be the goal of Snow White's evil queen, who seeks to eat her stepdaughter's heart and once again be the fairest in the land. Similarly, in Norse mythology, eating a dragon's heart gives Sigurd the power of prophecy.

Civilization vs. Barbarism
In The Irresistible Fairytale, Jack Zipes says, “Almost all cultures have cannibalistic ogres and giants or dragons and monsters that threaten a community. Almost all cultures have tales in which a protagonist goes on a quest to combat a ferocious savage. The quest or combat tale is undertaken in the name of civilization or humanity against the forces of voracity or uncontrolled appetite.” (page 8.)

In The Brothers Grimm: From Enchanted Forests to the Modern World, Zipes says something along the same lines: "Though each one of the Tom Thumb tales differs, they all focus on the same major concerns of The Odyssey as discussed by Adorno and Horkheimer: self-preservation and self-advancement through the use of reason to avoid being swallowed up by the appetite of unruly natural forces."

This describes the quests of Hop o' my Thumb, Jack, Gretel, and others. All three of these tales begin with families in extreme poverty, on the verge of starvation.
They begin with the hungry parents doing the unthinkable and abandoning their children in order to keep more food for themselves. Hunger thwarts the heroes again when birds eat their breadcrumb trail. Finally, they face a force trying to devour them. The tale reaches its happy ending when the heroes succeed, and in many cases even turn the monster's tools against them. 

Further Reading

• Warner, Marina. Monsters of Our Own Making: The Peculiar Pleasures of Fear.