Here's EXACTLY what you need to do to evolve. I'm trying to keep it spoiler-free, but beware, there are some spoilers.
Evolution Guide:
1) Complete the First Story (Ch. 1 - Ch. 20)
2) Graduate from the Guild - BOSS: Wigglytuff & Co.
3) Wait a few days, then talk to Mr. Mime by the Kecleon shop. - New Dungeon: Blizzard Island
4) Rescue Scizor from the dungeon that Mr. Mime tells you about - BOSS: Froslass
5) Wait a few days, then talk to Sunflora in the bottom of the guild. - New Dungeon: Surrounded Sea
6) Collect the Mystery Egg from the bottom of the dungeon that Sunflora tells you about.
7) Wait a few days, then complete Miracle Sea - BOSS: Gyrados
8) Wait a few days, then go to the bottom floor of the guild - New Dungeon: Aegis Cave
9) Complete Aegis Cave - BOSSES (Not all at once, in order): Regice, Regirock, Registeel, Regigigas + 4 Bronzong + 4 Hitmonlee *
10) Wait a few days, and Bidoof will come running to you telling you that there is trouble. New Dungeon - Mt. Travail
11) Complete Mt. Travail - New Dungeon: The Nightmare **
12) Complete The Nightmare **
13) Wait a few days, and visit Lapras. - New Dungeon: Spacial Rift ***
14) Complete Spacial Rift *** BOSS: Palkia - New Dungeon: Dark Crater
15) Complete Dark Crater **** BOSS (All at same time): Darkrai, Arbok, Mismagius, Rhyperior, Magmortar, Magcargo, Aggron
16) Recruit Manaphy
17) Wait a few days, and you will unlock Marine Resort. You don't have to complete it.
Any time after Chapter 20, you must recruit Dialga.
Any time after beating Darkrai, you must recruit Palkia.
Any time after beating Darkrai, you may speak to Cresselia outside of your base to recruit her.
* - Against Regigigas & Co. you team up with a Lopunny, a Medicham, and a Gardevoir. It doesn't matter if they die.
** - After completing this dungeon, you may not revisit it.
*** - On first visit, you may not leave. You still have access to a Storage/Save Kangaskhan rock.
**** - You team up with a Lv. 47 Cresselia. If she dies, you lose.