As far as dragons:
The Draconomicon says that dragons are innately magical - even on the biologic level. The phycial matter they eat plays only a tiny roll in their biology, preferences aside they can feed on rocks and dirt just as well as cows.
Raw magical energy is there primary sustenance.
So, we may presume that, in the primal start of this world, when seas of lava and water still clashed and the barriers between planes were raw and bleeding magic into the world, the first forms of life were the Elementals, born out of the unfathomable energies of the first days [Assume no planar travel, all Elementals and other such normally extraplanar creatures would be from this time.]
As time moved on, the energies were expended or absorbed into the elements of the world as they stabilized. [Giving the elemental energies as well as the foundation of material components]
In some places, the energies were still too great to be fully absorbed, and mutated the elements. However, the power needed to birth true Elementals was lost, so the transformation took longer and produced something else entirely. [These would be the progenitors of creatures with elemental subtypes, including dragons.]
While these primal cauldrons formed, portions of the new world were left without any of the magical energies, and the processes of life began much as they did on Earth. However, the energies of the primal cauldrons affected life lived long near them, producing mutations as the ages ground forward. [This is the foundation for most of the odd speciation, most of these mutations are very subtle and minor, but latter on will become the catalyst for larger changes.]
In time life emerged in a form we woudl recognize. However, so do did life we would not. From the primal cauldrons came things both strange and wounderous, and some terrible, all bound to the oldes magical energies of creation itself.
In the deep, Aboleth build an empire, and the first Dragons wared in the sky above. Other species were birthed, but most were forced to elude the most ancient to arise, else hide in the deep places under the earth [What can I say, I like Aboleths.

]
However, these ancient races, born from magic, were born dying. Without the energies of magic, they could not sustane themselves, and in time they fell into privative states, struggling to survive as individuals. [Thus any 'rare' race is limited - they have to have sufficient ambient magic, so are unable to sustane a concentrated population]
As these first titans withdrew, other life, magical and mundan, was free to develop. In some cases, the elders themselves devolved into more basic forms, giving rise to yet new races and species. [Things like drakes and dinosaurs could represent a species of dragon that adapted to lowering levels of magic.]
From this point on, it continues about as others have described above. I know I mostly focused on dragons above, but you can extroplate for any other highly magical race in much the same way.