Neither player can evolve normally (playing a card from their hand onto a Pokemon in play) on their first turn. You can evolve through other legal actions, though -- remember that effects are allowed to break the rules.
If you go second, you can use a Trainer (such as Rare Candy) that lets you evolve (but not if you go first, since you can't play Trainers).
And either player can use an attack (such as Phione MD's Evolution Wish) or a Poke-Power (like Caterpie GE's Pupate, or even Baby Evolution) that lets you evolve.