First came arceus
Arceus made D&P who made time and space, therefore the universe (Just a lump of dark matter at the current time)
Now Arceus had something to shove planets and stars and stuff into
Onto these planets he put more pokemon to regulate and shape them, in the case of earth;
Kyogre and groudon to form seas and landmasses
Regigigas to pull the continents into shape
The 3 Dogs to regulate fire water and thunder, and so on with all the aspects of the
planet.
At this point arceus would have either gone off and populated other planets (Dependin on if he did earth first, last or whatever) or gone to sleep up at spear pillar. Alternatively he may have created these pokes from himself, therefore stripping him of lots of power, (reducing him from a god to merely godley) so he went to sleep at spear pillar to regenerate until he was strong enough to populate the next planet along.
Now for the less concrete theories
As for the more mundane pokemon, this is the evolution bit. The world was populated by mew, a whole species of them. Since mewtwo was reated from a fossil this reinforces that not only were there multiple mews, but they were existant in prehistoric time. This would also explain why it contains every piece of dna, because all pokes originated from them. Some mews lived in the sea, and evolved into water types. Others lived indesert and evolved into the grounds. Mews slowly died out apart from the one that is left, who has sustained by living in the forest of the sevii island he is found on.
Now, to explain why there is only one left. Mew is like a stem cell, all other pokemon formed from him. This would require its biomolecular make-up to be close to perfect, so its body would be so efficient cells would be replicated as soon as they were destroyed, therefore mew would not age. the only way mew would die is of starvation, or by being eaten (Perfect cells leaves no room for mutation or disease). Some mews were herbivores, but those i the sparce deserts would be carnivores. If they migrated out of the deserts, they would see other veggie mews and eat them. This surviving mew had settled on an island in the sea (The sevii one), and because it is alone mew would eat little, and because it is surrounded by water the land would be fertile and mew would have an 'everlasting' food source, therefore allowing this mew to survive until 'present day'
So while this one merrily sat around and ate, the rest of the world was affected by darwin; Evolve or die. After millions of years any pokemon recognisable as mew had gone, leaving the one we play hide and seek with.