The Zoids Bible says that the titular zoids originally evolved from a planet seeded with zoid cores, going through eras of evolution uncannily similar to those of life on Earth, and the zoids shown are post-domestication beings.
In the original The Transformers comic book series, the Transformers themselves were once described as evolving from "naturally-occurring levers and pulleys". This was later Retconned into the Transformers actually having actually been created by a deity figure; the levers and pulleys thing turned out to be a theory they themselves had developed about their origins after having forgotten their true origin.
That said, the development of Micromasters, Pretenders, Powermasters, and so forth could be considered a form of this; a new mechanical trait is invented (symbiotic partnerships, a new type of tranformation disguise), and those with the new trait quickly outcompete those without, removing them from the story, if not from living.
In a Paperinik New Adventures issue, we know an alien race of robots. Their origin is unknown, but they're theorized either to descend from the computers of a ship who crashed on their planet, or to have evolved like every other race "only starting from microcircuits instead of microorganisms". Makes no sense, but who cares as far as it sounds so cool?
Films — Animated
Syndrome's master plan in The Incredibles was to build and evolve a robot by pitting it against gradually tougher Supers; eventually building a machine strong enough to take out his nemesis Mr. Incredible and wiping out the remaining Supers in the process.
But of course the machine evolves even more and is soon out of Syndrome's control
Films — Live-Action
The Terminator series, in many media. In a Robot War, the central AI Skynet notes what designs for its killer robots are effective and which aren't and feeds this knowledge into the design of next batch. One niche is filled by increasingly more lifelike humanoid robots able to enter survivors' shelters. Next on the list: emitting the strong smell of dog food.
Steven Spielberg's AI deals with the societal consequences of humans designing ever more intelligent and human-like robots, culminating in an autonomous robotic civilization surviving the extinction of humanity due to climate change.
The film Bicentennial Man, where the eponymous character decides to "upgrade" himself - becoming ever more human in the process. In the end, he dies of old age, because as he put it "I would rather die a man, than live for all eternity as a machine".
Literature
The Gaijin from Stephen Baxter's Manifold: Space are subject to this, with errors creeping in with each replication. A visit to their homeworld confirms that they were never built by anyone else but really did naturally evolve from scratch.
Gregory Benford's Galactic Center novels have "mechs" which evolved from self-replicating von neumann machines, after they were abandoned when their biological creators destroyed themselves.
In Gene Wolfe's The Urth of the New Sun, the mechanical humanoid Sidero is revealed to be a robot evolved out of spacesuits with built-in artificial intelligence.
Harry Harrison's short story The War With the Robots. With war becoming ever-deadlier, the retreating to bunkers deep underground, using robots to fight. The robots on either side design ever more effective robot forms, eventually able to drive the humans out of the opposing bunkers. The now-obsolete human race is shocked to find itself sidelined from what used to be their war.
An early example is Second Variety by Philip K. Dick, first published in 1953. The UN, losing a war with the Soviet Union sets up automated factories to produce "claws" — at first just mobile sawblades seeking warm bodies. Later the claws produce new, more effective designs which mimic human beings. The new varieties are able to infiltrate humanity, spreading paranoia as well as death. In a twist, the story concludes with the observation that some claws are developing weapons specifically to kill other claws.
The Isaac Asimov story "Found!" is about two astronauts repairing a satellite who find that it's now host to alien machine lifeforms that consume metal and oil.
In Poul Anderson's "Epilogue" two astronauts hit a Negative Space Wedgie and do not return to earth for millions of years. After a nuclear war, the machines left behind, which are already capable of self-replication, had evolved. It specifically says that radiation could damage the robot's data tapes just like it can human genes, thus letting them evolve. The mechanical lifeforms are unable to understand humans, and see them as entities with "poison under their skin" (oxygen). The humans use oxygen and eventually a transmitter in self-defense against them. The moon is worn but mostly unchanged.
A similar event happens with the roboticecosystem that developed on Titan in James P Hogan's Code Of The Lifemaker. Aliens send a mining colony, which gets damaged by supernova radiation and as a result ends up gone wonderfully wrong, with self-sustaining systems and, at the top of it all, sentient robots who are a Fantasy Counterpart Culture for late medieval to early modern Europe (about the time of The Renaissance; the humans who show up even call the robots' city-states by the names of those of Renaissance Italy).
Invincible, a novel by Stanisław Lem, is about an exploratory expedition discovering an ecosystem of micromachines, evolved from a lost alien civilisation's Colony Ship's robotic crew.
In The Cyberiad, the Tale Of The Three Storytelling Machines, Mechanical Evolution is discussed by some Ridiculously Human Robots, who trace their heritage from early Protomechanoans through the Missing Clink, all the way to Automatus Sapiens.
In Stephen Baxter's Evolution self-replicating robots evolve just like organic beings: software errors are possible in every new assembly, and those machines that benefit from theirs are more likely to reproduce at a higher rate. Mankind goes extinct without realizing that its automated Mars rovers will spawn a Galaxy-spanning civilization.
That's left unspecified by the story; the main characters could just as well be Energy Beings instead.
Especially since at the end they mention a "hydrogen core cluster intelligence" in a class 9 star that wants to get friendly.
The species that are referenced include one carbon-based race that "goes through a meat stage" (possibly Brain Uploading) and another that has a stellar plasma brain encased in a "meat" head.
In Code Of The Lifemaker an alien factory ship, designed to go to other worlds and set up automated factories to produce consumer goods to send back to the home system is damaged by the sun of a world it was preparing to land on going super-nova. Millenia later it crashes on Titan where its damaged systems attempt to fulfill their original programming of setting up factories and producing goods. Due to the programming errors and the attempts to deal with it a living robotic society evolves complete with various 'animals' and even separate genders (the software damage had the code for producing things like 'Fred' robots ending up split into halves producing male and female robots). A vaguely humanoid sentient robotic species develops and settles into a feudal nature with kings and religious dogma. Then humans find them and everything changes.
Live-Action TV
In the distant back-story of Caprica and Battlestar Galactica intelligent machines evolve into humanoid machines and leave their human masters to found a colony (named Earth) as their former masters are also forced to abandon their home and end up founding 13 colonies. On Earth, the humanoid machines build their own sentient robots — who themselves want to evolve and who therefore rise up to destroy all but five of their humanoid creators. Meanwhile, on the human colonies, people have created yet another generation of intelligent machines. The union of these two machine races finally leads to the creation of the human-model Cylons who appear in Battlestar Galactica.
And the union of those human-model Cylons and the Colonial humans along with another genetically compatible but unrelated planet of humans leads to the creation of modern human race, namely, us
The Replicators from both Stargate SG-1 and Stargate Atlantis both use this. The SG 1 Replicators as part of their story arc, the Atlantis ones as part of the backstory.
Mass Effect have the Geth, a species of rebellious robotic slaves have fled the populated regions of the galaxy and are developing their technology in a unique fashion. By contrast, most other species are following a common technological path, which looks like it will come back to bite them.
The Reapers consider themselves to be the pinnacle of all evolution (mechanical or otherwise). They see organic life as nothing more than a strange accident, useful only as something to be harvested when necessary to further the development of "true" life.
In both the Xenogears and Mega Man Legends video games, the heroes find out that the species on the planet are not humans, but evolved descendants from the biological parts of ancient human technology.
Present in Mega Man X in a rather unique form: all reploids are 'replica androids' derived from the titular X, who was designed with 'limitless potential,' the capability to evolve to (hopefully) overcome any obstacle he was presented with. This makes him simultaneously one of only two (actually only one) people capable of resisting The Virus and extremely important to the goals of The Virus: as he's forced to fight and evolve, more and more powerful reploids can be made based on him, allowing the species itself to evolve over time. This was mostly ignored after the first game in the original version (where it explains a sudden power-up after a Heroic Sacrifice) until it became relevant again in the eighth game: the remake of the first game placed more emphasis on it, with the Big Badaware that the more X fought and stopped their plans to Kill All Humans, the stronger his own forces would become.
As the opening cinematic for X3: Terran Conflict explains, terraformers are examples of a technology called artificial general intelligence, "mechanical minds capable of making themselves more intelligent, and again, and again, recursively forever." The intent was presumably to make the robots capable of adapting to unexpected events during the terraforming process, but somebody fouled up a software patch and they went haywire, turning into the Xenon.
Webcomics
In S.S.D.D the Oracle was designed to be self-improving, the rationale being that once it was running and debugging itself the programmers could be fired or imprisoned (they were hackers after all). In fact one of its programmers was an expert in evolutionary algorithms (see below), though he mostly created viruses that could mutate like biological ones.
Is it any wonder why the Oracle is the only AI capable of copying itself?
Although similar things happens to organic beings. Dragonfly, for instance, are now much smaller then they were, which requires less resources.
The general complexity of dragonfly has not decreased. They have become smaller in size simply because the atmosphere holds less oxygen than it used to, and their breathing mechanism isn't efficient enough to support a large body in these conditions.
The Dig-Bots from Sluggy Freelance keep on reproducing for several years, until they've created several variants like the Brain Dig-Bot, Bouncer Dig-Bots, High Priest Dig-Bots, and even Trash Can Dig-Bots.
Another inversion in Girl Genius. Agatha tends to compulsively construct little Clanks termed "dingbots". These dingbots can then go on to construct more dingbots, but dingbots are only so bright, so each successive generation gets less and less advanced, and less bright, and by the third or fourth generation the dingbots produced are nonfunctional.
In Questionable Content, Anthro P Cs (robotic companions) can "upgrade" their chassis. This happens at least twice, with Pintsize and Momo-tan, and works in conjunction with the fact that the author of the strip is constantly evolving his artwork.
Web Originals
Orion's Arm has many, many examples, including a planet with a machine ecology known as Stanislaw.
Western Animation
On Justice League, AMAZO's ability to evolve was so potent that by his second appearance he had even evolved beyond being a machine.
In the Futurama episode "A Clockwork Origin", Professor Farnsworth releases some Nanomachines to purify water on an uninhabited planet. Subsequent generations of nanites are more complex, and the situation very quickly gets far out of hand.
In Beast Wars, the Autobots and the Decepticons decided to change more energy-efficient forms called the Maximals and the Predacons, respectively, in an event called The Great Reformatting.
The "evolution" of the automobile through the years (along withMickey Mouse's) has been used as a parable of biological evolution in educative works.
YMMV on whether or not this is logical. It's certainly an example of evolution (change over time) but the analogy would really be for Intelligent Design (at least if the designer was doing it on the fly each generation) than for Natural Selection (or some combination there-of if that even makes sense: an intelligent designer deciding which traits to continue, which to change, and what new things to add based on the competition between models and market forces)
