Speak to any innkeeper in an inn or a tavern across Skyrim to start this quest. Ask them if they have heard any rumors lately. Repeat until they tell you about the Shrine of Azura. An objective should now appear under your misc objectives tab in your quest log: Visit the Shrine of Azura.

To reach the shrine of Azura, first travel to Winterhold (either fast travel, or by carriage). Then, head south, and up the trail leading you onto the mountain (Use horse if you have one to get there faster as it's a long road). Check your map for your progress. Eventually, cut Southwest and keep going up a small path. When you reach the Shrine of Azura, climb up some stone steps near a big statue and speak with Aranea Ienith.

Aranea Ienith: Azura has seen your coming, traveler. It was not curiosity, but fate, that has led you here.

You can answer:
"Seen my coming"? What do you mean?
What is this place? Who's Azura
I don't believe in fate

Try the first option, and she tells you that Azura has given him the gift of foresight. She had a vision of you walking up the steps to this alter long before you were born. You have been chosen to be her champion. Aranea knows that this is unexpected, but don't worry as it will all unfold as Azura has predicted.

Your options will now be:
Very Well. What does Azura need?
I'm not anyone's champion. Find someone else.

Choose the first option. She tells you that you must go to a fortress, endangered by water, yet untouched by it. Inside, you will find an elven mage who can turn the brightest star as black as night. It is cryptic, but Azura's son are never wrong. The fortress may refer to Winterhold. Ask if they know this elven enchanter.

This will start the quest The Black Star. Open your quest panel for details:

The Black Star
Aranea, a priestess of Azura, says I am destined to find "an elven man, who can turn the brightest star as black as night". She believes he is in Winterhold.

Your first task is to find the elven mage from Aranea's vision. Go back to Winterhold, then to Frozen Hearth Inn. Ask Dagur, the innkeeper, if there is an elven mage there that studies the stars. He tells you that all the mages are up in the college and to ask them if they will let you in. But Nelacar might know too. He is an old timer from the college, but has a room at the inn. Your new task will now be to speak to Nelacar.

Nelacar is in a room nearby, possibly sleeping. Or he might be arguing with the innkeeper about a failed experiment. Find him and talk to him. Tell him you are looking for an elven mage who studies stars. Nelacar tells you that Dagur and him have an understanding, Dagur gives him privacy and he makes sure his experiments don't blow up the inn. Nelacar then asks you who sent you, if it was the college or the Jarl. You will eventually be presented witht he following options:
A priestess of Azura sent me (PERSUADE)
Look, I'm willing to pay (BRIBE)
I don't agree to anything, talk (INTIMIDATE)

If your speech skill is not that high, bribe Nelacar because that should always work. Otherwise, if you are confident enough about your speech skill, try to either persuade or intimidate him. Intimidate is easier then Persuade. If your persuade speech check fails, he mocks you about claiming that you work with the Daedra, treating it as a joke, and wants you to now tell him the one about the Argonian Maid and the Lusty Baron.

Nelacar asks you what you know about soul gems. You can answer:
They're for enchanting, correct?
Soul gems? Why are you asking?
Don't change the subject

Choose the first option. He tells you that you are right, except that the soul gem is always consumed. They're frail. Except for one. Azura's Star. A Daedric artifact that allows any number of souls to pass through it. Some of them wanted to find out how. Nelacar was working under Malyn Varen. If only they knew what he was really planning.

Ask Nelacar what Malyn did or to get to the point. He tells you that Malyn wanted to alter the star. He was dying. He thought he could store his own soul inside. Become immortal. It drove him mad. Students started dying. Eventually, the college exiled him. He took a few loyal disciples to Ilinalta's Deep and vanished. Nelacar does not care who asked you to find the star, but he tells you not to take it back to Azura. The Daedra is evil, they're the reason Malyn went insane.

Your task will change now to "Find Azura's Star". Your quest log shows the following update: Nelacar has told me that his old mentor, Maylyn Varen, was experimenting on Azura's Star. Malyn's last known location is Ilinalta's Deep. To get to Ilinalta's Deep, travel west from Riverwood past Bleak Falls Barrow, and through the mountain trail onto the shore of a big lake. If you have been to Fort Greymoor previously, fast travel there and head south through North Brittleshin Pass to save some time.

Explore the waters, and locate a trapdoor on one of the sunken towers. Inside, at the beginning of the dungeon, you will also find a chest that contains Shalidor's Insights, a book needed for one of Urag's quest. Make sure to check underwater for doors or chests. Fight your way through skeletons and necromancers, and reach the door to Ilinalra's Deluge. Head up a big spiral staircase. You will eventually reach a throne room with the skeleton of Malyn Varen, and a Broken Azura's Star at his foot. Take the Broken Star and you will be presented with a choice of what to do next, either:
Bring the star to Aranea, or
Bring the star to Nelacar

Your quest log is also updated: I have Azura's Star, but it's been corrupted by Malyn Varen's magic. I could take the Star to either Aranea or Nelacar to have it repaired.

Tip: If you are serious about enchanting, you should take Star to Nelacar. If you don't use enchanting much, take Star to Azura instead.

First Option: Bring the Star to Aranea

If you choose to bring the Star to Aranea, go back to the Shrine of Azura. Aranea tells you to hand over the Star so that she can ask Azura to restore it to its original purity. You can say:
Here. Take it.
I need a moment. I'll be back later.

Choose the first one, unless you are having second thoughts about who to return the Star to. The priestess takes it and communes with Azura. Azura wishes to speak to you herself. Speak to Azura. She thanks you for rescuing the Star from Malyn Varen. But his soul still resides within, protected by his enchantments. Until he is purged, the artifact is useless to you. You can ask:
Is there any way to cleanse the Star?
Then why don't you remove it? Aren't you a daedra?

Azura tells you that eventually the Star will fade back into her realm in Oblivion. But she doubts you have the hundred or so years it would take to wait. Only one option remains. She will send you inside the Star. You will banish Malyn's Soul. Tell Azura You're ready to enter the Star.

Second Option: Bring the Star to Nelacar

If you choose to instead bring the Star to Nelacar, go back to the Frozen Hearth Inn in Winterhold. He wants to finish Malyn's work. It would mean cutting the Star off from Azura. Only Black Souls would be able to enter it. You can say:
Let's do it
I'd like to think about it

Choose the first option, unless you have changed your mind and want to bring it to Azura instead. Nelacar takes the Star from you and examines it. He tells you that Malyn actually managed to trap his own soul inside the Star. But it's falling apart. It needs more and more souls to sustain itself. The Star is being used to sustain Malyn's soul. Nelacar cannot fix it while that fragment of him is inside. You can tell Nelacar:
So we need to deal with Malyn somehow
Won't that kill him?

Choose the first option. Nelacar tells you it is not as simple as enchanting Malyn away. He's put up Barriers. Souls are only allowed in, not out. If we were to somehow send a soul inside the Star, one that was ready to overpower Malyn from the inside...

You can say:
I don't like where this is going.
You want to send my soul inside, don't you?

Choose the second option. He tells you it is a special type of soul trap. Placing you inside the Star without fully killing you. Once Malyn has been dealth with, Nelacar will bring you back.  Your new dialog choice are:
I'm ready to enter the Star
What to do once I'm inside
What's to keep me from ending up like Malyn?

Tell Nelacar you're ready to enter the Star.

The Black Star - Quest Conclusion

Whichever quest branch you chose (Aranea or Nelacar), you are now sent into the Star itself. Inside, you find the soul of Malyn Varen

Malyn Varen's soul: Ah, my disciples have sent me a fresh soul. Good. I was getting... hungry. Wait. There's something different about you.

You can say:
You can't escape your fate, Malyn
This experiment of yours is over!

Tell him his experiment is over. Your objective is to Destroy Malyn Varen's soul. Fight him and the Dremora he conjures. Once you have killed all the enemies, your soul will be pulled out of the Star (either by Nelacar or Azura). Be sure to quickly loot Malyn before being pulled out.

If you return to Nelacar, ask him what to do with the Star now. He says you could use it for what they meant if for. Using black souls for enchanting. The Black Star is a multiple, unlimited use, Black Souls Gem. It can store human souls.

If you return to Azura, she tells you that you are free to use Azura's Star as you see fit. Arnea is unlocked as your companion as Guardian of the Star. Azura's Star is a Multi-Use Grand Soul Gem.