Questline

Talk to the Yggdrasil Gatekeeper at (nyd_dun02 99, 199).
How to reach the gatekeeper:
Enter Yggdrasil Dungeon at (spl_fild01 368, 112).
Enter the portal located at 3 o'clock of the map (nyd_dun01 252, 144) (not shown on minimap). The portal markings on the minimap are exits only.

Once in level 2, walk right until you've reached a cliff. Control the "Strange Device" at (nyd_dun02 137, 274), and cross the canyon by stepping on the circles. Stepping anywhere outside the shown circles will return you to the bottom right corner of the previous map. (Rogue-type classes can use Stealth. Be sure turn off Stealth when reaching the last circle to make sure the next circle appears.)

After crossing the cliff, follow the path consisting of stairs and roots until you've arrived at a gate at (nyd_dun02 99, 199).
Tell Commander Agip (mid_campin 90, 121) about the cave you found, he tells you to find Historian Magnifier.
Ask Historian Magnifier (mid_camp 271, 299) for help. He tells you to visit his assistant in the Prontera library.

In the west Prontera Library (120/264), talk to Assistant Naomi (prt_in 171, 94), and she will give you several papers to read.
Return to Magnifier, he tells you to go investigate what the Laphine and Sapha know. Chose to go to either the Laphine or Sapha.

Laphine:

Talk to the Grumbling Soldier in the Splendide (splendide 198, 178), and ask him about the tree.
Go inside the central building (splendide 197, 191).
Then speak to Commander Lebiordirr (spl_in01 110, 60).

Sapha:

Inside the building in the far right of Manuk (309, 142), talk to the Laphine Prisoner (man_in01 291, 62).
Talk to Neat Etorr (man_in01 311, 57) in the same building.
Return to Magnifier, he tells you to speak to Commander Agip to get his opinion.
Commander Agip decides to ask both tribes for help exploring the cave. This will force each to help you to prevent you from getting help from their enemy.
You are presented with a choice of which tribe to go to in order to seek assistance.

Laphine Branch:

Speak to the Laphine Commander, and threaten to ask the Sapha's help if she refuses hers. She will agree to help and ask you to talk to Aide Arioss.
Aide Arioss (spl_in01 104, 56) will give you a token to mark you as a guardian of the Yggdrasil and tell you the password to get past the door.

Sapha Branch:

Return to the building in Manuk and talk to Neat Etorr again.
Talk to the Laphine Prisoner twice.
At this step you can now enter the Nidhoggur's Nest Instance. After you clear the instance, talk to Yggdrasiliad in the final room.
Chose if you want to go to Splendide or Manuk for your reward.

Splendide:

Talk to the Laphine Commander, and then Arioss. You will receive 150,000 Base EXP, 3,500 Job EXP, and 10 Splendide Coin.

Manuk:

Talk to Etol, and then with the Laphine Prisoner. You will receive 150,000 Base EXP, 3,500 Job EXP, and 10 Manuk Coins.

Guardian of Yggdrasil