Rebuilding the Gatekeeper
After talking to Sheogorath, find Relmyna in the ruins of Xaselm. She's on the third level of this dungeon, deep inside her laboratory called Sanctum of Vivisection. After a short conversation she gives you the list of ingredients she needs to create a new Gatekeeper.
In order to get the ingredients, go to the Gardens of Flash and Bone - the dungeon that you've already passed by, at the very beginning.
First two plants can be found in Conservatorium Corpusculum.
The third ingredient, Essence of Breath, is in Caverns of Resurration. This level is quite a labyrinth, so watch your step and try not to get confused.
The final plant is in Notatorium of Wound Bled Tears. When you have them all, go back to Relmyna. She orders you to choose the Gatekeeper's body parts - go towards the map markers and make your choices there, selecting the head, hands, torso, legs, and heart that you like best. Tell Relmyna that you're done and she'll tell you to meet her by the Gates of Madness.
HINT: You can ask Relmyna about her victims and convince her to stop tormenting them. If you agree to take their place, next time you talk to her she'll give you Manacles of Pain.
Go towards the map marker and see through the ritual, throwing ingredients into the pool when asked to. When it's over, you'll get a Summon Flesh Atronach spell. You can now go back to the palace.
The Helpless Army
Your conversation with the Prince of Madness will be interrupted by one of the guards who enters the room and tells you that a guardian stronghold is under attack. If you're Duke of Mania, you'll have to help the Mazken in Pinnacle Rock. If you're the ruler of Dementia, it'll be Aureals in Brellach.
HINT: This quest is virtually identical in both Pinnacle Rock and Brellach: even the dungeon maps are the same.
When you're at the spot, talk to the remaining guardians' leader. Tell her that you're ready to attack.
When you're in Hall of Reverence, you can open the gate that's blocking your way (1) using the button upstairs (2). Use the chime (3) to crush the crystals that form the guardian leader's prison (4). Talk to her and together go to the next level (5).
At the beginning of the next level, all your companions will suddenly die and you'll be left alone. Use another chime to open the door. When you're in the big room in Font of Rebirth, use the four chimes in all corners of the room (*) to destroy the crystal in the middle and restore the guardians' lives. Their leader will gratefully give you a summon Mazken/Aureal spell (the one you don't already have). Go back to the palace.