Skyrim Walkthrough: Ep. 75 The Black Star

To start this quest you need to go to an inn and ask the innkeeper if he/she has heard any rumors lately. They will tell you about the Shrine of Azura which will start the Black Star quest and give you a quest marker to the shrine. You can find the shrine south-south-est of Winterhold on top of a mountain.

She will ask you to find the mage that knows something about the Black Star. He is located in the inn at Winterhold. You can talk to the innkeeper and you will get a quest marker for the location of Nelacar. For me he was in one of the side rooms of the inn at Winterhold.

Ilinalta's Deep:
This former tower is full of mages. The main problem that mages poses is getting close to them. Once you can use your sword or any other close combat weapon on them they will die very quickly.

The best way to take out mages is to use bow and arrow. Be sure to be sneaking because often times you can one-shot mages with a good bow and some decent arrows.

Snealing is also very powerful when using a sword or similar close combat weapon. I usually like to use the Wabbajack on stronger enemies because it has a chance to instant kill them or turn them into a chicken or rabbit for a while which will let you get close to them easily. You can find a full guide to getting the Wabbajack here.

Inside the Black Star:
After you have collected the black star at Ilinalta's Deep you have a choice. Either you can bring it back to the shrine were you will receive a soul gem that traps non-human souls or you can go back to Nelacar from whom you will receive a star that traps human souls. That is what I went with because a human soul is always the best soul possible.

To get the soul gem you will have to enter it. Inside you meet 3 Demora Markynazs and Malyn Varen. You can use the same strategy I outlined earlier to defeat these enemies. Remember the loot the Demora Markynazs because they have deadra hearths on them