In their universe, rather than evolving slowly from a humanoid race on a twin planet to Earth, these Cybermen were instead created by an insane human called John Lumic. He wanted to create a race that would never age, never die, and more importantly, never go extinct.Doctor had not been there by pure fluke. He was able to limit the development of the Cybermen and destroy their new-found Cyber-Controller (actually an upgraded Lumic). However, within three years (in parallel time) the Cybermen were able to cross over to our universe and wreck havoc. Had the Daleks not been around already wrecking a havoc of their own, the Cybermen may have upgraded the unprepared Earth. As it happens, the Daleks kicked the bolts off the Cybermen and they were all pulled into the Void between Universes by the Doctor.
The Parallel Cybermen still existed however, because of a simple yet effective way of imprinting their existance on our world. Only life forms that had travelled through the Void could be pulled back in, so the Cybermen that were created from our universe using resources from our universe remained, being called the Cyberman Remnant.