Evolution in Spore is highly simplified to bypass the complex issues usually associated with the evolution of creatures on Earth. Starting off in the Cell stage as a single celled organism you gain energy, until a point in which you can upgrade yourself using the Cell Editor to add appendages. For example in the Creature stage you have to kill/befriend to get DNA points. You can lay an egg and this takes you to the Creature editor where you can shape your creature and add / remove body parts. As you go on, the view pans out as you enlarge in size and complexity. The GDC video lacks footage of the transition between the microbe and the Creature stage, but evidence suggests that there will be a point where you will 'jump' to the next level (See: Saltation). That is you will lay an egg, gain access to the editor, and will be able to access new parts that will allow creatures to exist. For example, the "legs" of a microbe may progress into full fledged fins that allow swimming. The cross from Will Wright's aquatic creature to land creature was done in the same way. The editor did not show any signs of complex things such as lungs, but merely the removal of the fin and addition of legs 'forced' the game to choose a land environment. The creature can be seen walking from the ocean on to the land without any other changes made. It can be assumed that all issues are simplified down to the most basic of ideas and theories, complex science being ignored in order to make game-play simple for the younger of us. Note: For those concerned about lungs, all air is compatible for all species.
In real life evolution is much more complicated than in Spore. While in Spore, your creature evolves along a simple path toward sentience, real creature undergo various forms of physical and mental evolution to adapt to physical changes in their environment, not necessarily increasing in brain size over time. Furthermore, all creatures on Earth are descended from a common ancestor, and even in more recent eras creatures have branched off to split into several different species. However, in Spore all creatures seem to be completely unrelated to each other, and all follow a separate evolutionary path, evolved from entirely separate ancestors.