They say that blood smells and tastes like iron. I don't think this is literally true, but somewhere, back in time, someone no doubt burned blood and got rust. That's my theory for how the bond was first established.
Ironically, the red color of blood doesn't come from iron: Fe(II) is light blue in color and Fe(III) is yellowish brown. The intense color comes instead from the molecular scaffold supporting iron atoms in hemoglobin. A ring of rings, with each little ring bearing a nitrogen base, stabilizes an iron, which otherwise would irreversibly find oxygen and turn to rust. The so-called porphyrin ring supports the otherwise unstable iron and allows it to reversibly bind and transport oxygen throughout the bloodstream. The word porphyrin comes from the Greek word meaning purple. Even with central iron atom plucked out, porphyrin is a deep purple in color.
There's lots of blood history surrounding the word porphyrin. King George III famously suffered from porphyria. Could this be the source of our political term blue blood? There's more medical history on porphyria here.
*The reddish color of Mars comes from a skin-deep layer of iron oxides.