A Door In Niben Bay
Reach the spot shown on the screenshot below to find a new island in the middle of Niben Bay. In there, you'll see a portal that leads to Sheogorath's domain. Talk to Gaius Prentus and help him defeat an aggressive Dunmer. In a few seconds you'll hear the Prince of Madness calling to you. Nothing to do but to go through the portal.
You'll find yourself in a modest room, where you'll be greeted by the prince's most loyal servant, Haskill. Sit in front of him and talk to him twice, agreeing to enter this daedric plane.
Through the Fringe of Madness
You're now in an area known as The Fringe. Go to a local village called Passwall to talk to Felas and Shelden. Follow them and you'll see the Guardian taking care of some adventurers. As you might have guessed, your task will be to eliminate this monster. Talk to both men once more and you'll be told that Jayred Ice-Veins is actually planning to assassinate the Guardian. Find him somewhere in the area and offer your help. He'll lead you to the Gardens of Flesh and Bone. Open the gate using the lockpick and talk Jayred defeat the Shambles.
When it's all over, Jayred will tell you that he's going to prepare some custom arrows for you and they'll be ready in a few hours.
Enter the inn (Wastrel's Purse) and talk to Relmyna Verenim. She'll tell you to go bother Nanette Don. Find her and ask her about the Gatekeeper - some Speechcraft will be in order. It'll turn out that Relmyna visits the monster around midnight every single day. Wait until 12 am and follow the dark elf sorceress on her trip. After a short scene, pick up the tissue she dropped. You can use the tears that it was soaked with to poison your weapon.
Go back to Jayred's place and tell him that you're ready. You'll both go and fight the Gatekeeper. You'll get 20 Bonekeeper Bone Arrows from Jayred, use them to deal some extra damage. Don't forget about Relmyna's tears! When you bring the beast down, take the keys from its body and talk to Haskill who's shown himself to congratulate you. It doesn't matter which gate you choose now, you can travel between Mania and Dementia freely at all times. The only difference is the spell you get when crossing the gate: Blessing of Mania or Blessing of Dementia.
To keep up with the main quest of Shivering Isles, go through the whole island all the way to New Sheoth, and then reach the palace (SI33).
A Better Mousetrap
When you finally meet Sheogorath in person, he'll send you on a quest to restore Xedilian to its former glory as a prison for troublesome adventurers. Talk to Haskill once more to get further instructions.
Use the button to the right of the door (1). Defeat the Grummites and push another button to go even further. Just after the gate, use the third button (2). Near the Judgement Nexus (3) defeat a Grummite Shaman Torturer, then grab his staff and activate the mechanism. Go further to reach a statue with a button on it - push it.
In the next room defeat some more Grummites and grab another Shaman's staff. Activate the second Nexus (4) and go to Halls of Judgement (5).
Find the final Shaman and activate the last Nexus (6). A door will open, it will lead you to the Resonator. Defeat all the enemies on you way and switch on the mechanism (7). Use the teleport to the right (8).
Baiting the Trap
You'll meet Kiliban Nyrandil, a local caretaker. He'll explain to you that you are to deal with some adventurers that entered the dungeon. There are three rooms before you: in each one you have to make a decision whether to activate a deadly trap or try to drive the prisoners crazy by using some more gruesome techniques. Kiliban will explain everything at each step. Your choices don't really matter as for the quest's outcome, so just have fun.
When you eliminate all three adventurers, talk to Kiliban once more. You'll get a cool sword - Duskfang (or Dawnfang). Each time you kill 10 enemies with it, it gets stronger, but unfortunately is reset every 12 hours.
When you try to leave the dungeon, you'll be attacked by Knights of Order. Defeat them and ask Kiliban about the situation. Go back to Sheogorath's palace.
The Lady of Paranoia
When you're back, the Prince of Madness will order you to get acquainted with the dukes of Mania and Dementia. First, pay a visit to Lady Syl, who resides during day hours in nearby House of Dementia. She'll tell you to take Herdir with you and investigate the matter of a conspiracy among the servants.
Go to Crucible and ask some random NPCs about the conspiracy. You can tell Herdir to torture the interrogates if you feel like it. In my case it was Ushnar gro-Shadborgob who told me that I should talk to Anya Herrick. Find and interrogate her, asking Herdir to do some of his magic on her. She'll point you towards Ma'zaddha. The Khajiit won't be too keen on telling you anything, even if you torture him. Ask around the town about him (try Sickly Bernice) and you'll know that he's been secretly meeting one of the city guards during late night hours. Spy on one of these meetings (use the map markers to know where to go) and tell Ma'zaddha that you've heard everything. He'll agree to help you. One day later, you'll find him dead in his house. Search the body, go upstairs and look in one of the cupboards. You'll find Nelrene's sword and a letter.
Go to Nelrene and she'll confess that she's been working under orders from Muurine. Pay a visit to the old lady and she'll confess as well. Go back to Lady Syl and have the honor of watching Muurine get killed in the torture chamber.