Morrowind:Recovering Cloudcleaver

Quick Walkthrough
#Meet Hlormar Wine-Sot at the roadside northwest of Caldera.
#Find the Witch Sosia Caristiana down the road.
#Decide who to help.

Detailed Walkthrough

A half-naked Barbarian
Northwest of Caldera, you will run into a half-naked Nord on the road. Hlormar Wine-Sot will tell the tale of being seduced by a witch, paralyzed, and robbed of his prized Cloudcleaver axe, and almost all of his clothes.

Find the Witch
Hlormar will say that he believes the witch's camp is towards the northwest. Escort Hlormar and follow the road to the northwest, taking the north path at the first intersection. (Strangely enough, she is located not too far away from another witch-troubled barbarian... hmmmm). Find the Witch Sosia Caristiana who will tell a different tale. Sosia says that she hired Hlormar as an escort but he became too friendly so she cast a sleep spell on him and took his possessions as a lesson. She believes Hlormar is too angry and decides that she will not give the axe back yet, instead offering that she will meet with Hlormar in three days at the Caldera Mages Guild and give the axe back then. Talk to Hlormar about this offer and he will reject it, forcing you to choose a side in the conflict.

Whom to Help?
If you side with Sosia, Hlormar will attack and you will have to kill him. Hlormar is a bare-handed fighter who can quickly knock an unprepared hero with insufficient Fatigue to the ground. Once he is defeated, Sosia will thank you and give you some potions for your troubles (Exclusive Restore Health, Quality Restore Fatigue and Quality Fortify Health).
If you side with Hlormar, he will attack Sosia and you can join in to kill her. Note that Sosia attacks with a Steel Staff of Chastening, which damages personality and luck attributes. Loot the axe from her corpse, along with the staff and the potions she'd have given you if you took her side, and Hlormar will notice immediately, giving you the option of giving Cloudcleaver back to Hlormar or not:
If you keep the axe for yourself, Hlormar will attack you as mentioned above.
If you give Hlormar the axe he will be happy and offer you some fighting tips that will increase your strength attribute by 2 points. A potential suggestion is to have him raise your strength, and then attack him to retrieve Cloudcleaver, thus getting both an increase in strength and Cloudcleaver. You may also pickpocket it from him.

Notes
An alternative way to complete the quest is to pickpocket Cloudcleaver and give it back to Hlormar. This will skip the fight but nets the same reward from Hlormar. This does not work for unpatched versions of the game however.
If you decide obtain Cloudcleaver by pickpocketing or killing Sosia before talking to Hlormar, Hlormar will automatically engage in a conversation with you. It is not possible to return his axe, and closing the dialogue window will immediately open a new one, effectively breaking the game.
Hlormar will not increase your strength above 100.
At the conclusion of this quest, Hlormar will stay in place and remain naked indefinitely.
Siding with Sosia and killing Hlormar when he attacks you will result in the quest not being counted as completed in the journal

 

Quest Stages