In the new Doctor Who series the Cybermen come from an alternate universe and an alternate Earth. In the old series the Cybermen came from our universe. So what happened to them?
The Cybermen were last seen in the Silver Nemesis serial (this one is quite famous, because it was the 25th - Silver - Anniversary of Doctor Who, and the 150th televised story, and episodes 2 and 3 were the first to premier outside of the UK, in New Zealand), featuring the 7th Doctor (and Ace).
The serial is centered around restoring a living statue (made of validium), which was a tool made by Omega and Rassilon as a defense for Gallifrey. In the serial
the statue wipes out the entire Cybermen fleet.
However, that's only the last time that we see the (Doctor Who universe) Cybermen in the Doctor's timeline in a televised episode - it's not the latest time that they have been seen.
The 8th Doctor encounters the Cybermen in 2006, when Cybermen try to invade Earth via a portal in the audio drama Human Resources. I believe this was the last time in the Doctor's timeline that he encountered the (Doctor Who universe) Cybermen.
The 6th Doctor comic The World Shapers reveals what finally happens to the Cybermen (some time after the 101st Century):
They become beings of pure thought/energy, and completely peace-loving - they indeed redeem all sentient life.
There are other stories that feature the Cybermen between Silver Nemesis and their eventual end, such as:
I consider the audios canon, and David Banks's Cybermen book goes some way to explain the cybermen.
With regard to:
More confusing is that nearly every time the Earth is attacked by Cybermen, it is the first time. We will have to blame that on time travel.
It's easily explained that they are all different factions of surviving Cybermen.
It seems likely the alternative Cybermen in the new series have melded with the Doctor Who universe ones. Plus rumour has it a redesign and return are on the cards next year.
Planet Mondas was an alternate Earth. It even had the same continents as Earth, just upside down. The details of the pseudoscience explaining where Mondas is located changed from The Tenth Planet to Rise of the Cybermen, but that's no different to the modernized special effects.
More confusing is that nearly every time the Earth is attacked by cybermen, it is the first time. We will have to blame that on time travel.
The Original Cybermen from Mondas survived in our universe and made a return in the episode "A Good Man Goes to War". You can make the distinction between the Cybus Cybermen and the original Cybermen by the logo on their chest. It was also written in the Brilliant Book of 2012 that this was most likely the case.
"According to comments made in The Brilliant Book 2012, the Cybermen of the Cyber Legions were the original Mondasian versions because, despite having the Cybus-style suits, they lacked the "C" logo on their chest. If so, the Cybus Industries Cybermen joined the Alliance and the Cybermen that have appeared since then (without the "C" logos) are the Mondasian models."