Genesis of the Cybermen
The creation of the Cybermen in the Doctor's universe occurred on the planet Mondas some time prior to the 20th century.
History
Cybermen of the Doctor's universe
One account stated the planet Marinus was an earlier name for Mondas. According to this account, the Voord acquired Worldshaper technology to accelerate time and turn themselves into full cyborgs. The Cybermen later remembered this planet as Planet 14. (COMIC: The World Shapers)
Another account did not explain the earliest origins of the Cybermen, but showed Cybermen existed on Mondas alongside the Lizard Kings, the Mondasian versions of Silurians, as well as the Sea Devils. These Cybermen died out until centuries later when Mondasian archaeologists discovered the remnants of ancient Cybertechnology. Presumably, the Mondasians recreated the ancient Cybermen. (COMIC: The Cybermen)
Yet another account showed that as Mondas travelled beyond the outermost planets of the solar system, conditions on the planet deteriorated. The Fifth Doctor and Nyssa arrived on Mondas prior to the rise of the Cybermen. They discovered the survivors living in an underground city roughly on a parallel with Britain in the 1950s, although with more advanced technology. They witnessed the Mondasians slowly slide towards cyber-conversion, as the Faction had. The Mondasian cyber-conversion program was conceived by the cybernetic gestalt intelligence controlling Mondas as a solution to the planet's increasingly desperate situation. These early Cybermen were, however, plagued with serious design flaws and the conversion method proved very unstable as the biological systems of most of its unfortunate victims would fail soon after they were turned, causing most subjects to perish. The conversion project's chief scientist, Doctorman Allan, managed to discover a solution when the Doctor was captured by Mondasian police. By using data extracted from a forcibly biological analysis of the Doctor, she discovered an extra brain lobe unique to Time Lords, dedicated to mechanical and other bodily functions. She was able to replicate this trait into a new Cyberman prototype, greatly increasing the survival rate of the newly converted. The Doctor was horrified about his unwilling hand in the creation of the Cyber race, so much so that he tried to derail history by poisoning the Cyber-Planner before it could manage to convert the entire population, and afterwards he helped the Mondasians with starting a research program into how to undo the conversion process. However, after the Doctor and Nyssa's departure, it turned out his efforts were ultimately in vain as the Cybermen soon overpowered and converted the remaining Mondasians. (AUDIO: Spare Parts)
The Cybermen evolved and changed on Mondas. The CyberFaction, a group dedicated to more radical cyber-conversion, moved to Planet 14. The Mondans stayed on their home planet. (PROSE: Iceberg, REF: Doctor Who: Cybermen)
Another account states that at least one group of the Mondasian Cybermen were first created on a Mondasian colony ship. The ship was in orbit of a black hole and as a result, time in the top of the ship ran faster than the bottom where the colonists lived. With their ship old and becoming uninhabitable, the colonists began transforming themselves into Cybermen under the guidance of "Razor" as part of "Operation Exodus" in order to become stronger so they could leave the ship and survive. In truth, "Razor" was really The Master who, after turning Bill Potts into a Cyberman, declared it to be "the genesis of the Cybermen" to the Twelfth Doctor and his future self. (TV: World Enough and Time)
Other universes
Independently, John Lumic, the CEO of Cybus Industries, created the Cybermen of a parallel Earth. (TV: Rise of the Cybermen/The Age of Steel)
Behind the scenes
Continuity contradictions
Taken at face value, the origins of the Cybermen given in the Doctor Who Magazine comics feature The Cybermen conflicts with that given in Spare Parts and neither accords very well with The World Shapers, which had earlier appeared in Doctor Who Magazine. Lance Parkin has speculated that perhaps Cybermen have originated in different planets and times independently, just as they had in different universes, as illustrated by the parallel universe Cybermen having no connection with the Cybermen of the main universe.
Alternatively, the Cybermen shown in The World Shapers may have preceded the ones in The Cybermen, though they do not match visually. (The former resemble the sleeker, later Cybermen while the Cybermen of The Cybermen resemble the ones of The Tenth Planet.) The explanation of the creation of Mondas by the Constructors of Destiny in The Quantum Archangel also contradicts that given in The World Shapers.
"Genesis of the Cybermen" storyline
Gerry Davis, who had co-created the Cybermen with Kit Pedler, had written "Genesis of the Cybermen", an outline for a Cybermen origin story which David Banks included in his Doctor Who: Cybermen.