To start, you either have to go through the maze, or have Completed The Grand Tree quest and use the Spirit Tree in the Gnome Stronghold to get into the Gnome Village.
If you are going through the maze, it is recommended to enter from the north-west entrance and follow the below path:
Squeeze through the fence, and head east and speak to King Bolren near the Spirit Tree. Ask if you can help him. He will explain that the spirit tree and orbs of protection protect the gnomes, but they became desperate and brought one orb to the battlefield.
Khazard troops seized the orb, and now they're defenseless. He will ask you to retrieve the orb.
You will be guided out of the maze by Elkoy. Go east, and look for Commander Montai. He is the only gnome wearing a red hat and shirt. He'll ask you for 8 regular logs to better their defenses.
If you brought a hatchet to cut yourself, the nearest trees are west of the Maze. Bring him the logs, then talk to him again. The next phase of the plan is the use the ballista to knock down their stronghold walls. But, they need the exact coordinates.
The First tracker Gnome is located north of the Khazard troops' building.
The Second tracker Gnome is in the smaller building to the east, in the jail cell.
The Third tracker Gnome is in trees to the west/south-west. He has gone insane. You will eventually ask for the coordinates, but will he won't make too much sense. There are a bunch of different things he can say, but this changes per person. You may have to guess some.
When you have talked to all of the Tracker gnomes, fire the Ballista near the War Tortoises. If the last coordinate is right, you will get a message saying it flies right into the Khazard Stronghold.
Head north, and climb over the low wall in the stronghold building, just south of the first gnome tracker. Kill the Khazard commander that attacks, then climb up the ladder. Try opening the chest in the north-east corner, but another commander will attack.
Kill him, and then search the chest for the orb. Return to the entrance of the maze, and talk to Bolkoy to follow her quickly through the maze. Talk to King Bolren.
Khazard troops came in the night, killing anyone in their way, including his wife, and took the other orbs.
Go north from the Khazard stronghold, then west, then north, to find the Khazard Warlord. Once he is dead, you will get the orbs.
Return with the orbs to the Gnome Village and speak with King Bolren. They will begin a ceremony for the Spirit Tree.