To begin the quest, talk to the Innkeeper and choose 'Helping the Innkeeper'. He will tell you the following:
Helping the Innkeeper
You've proven to be a very capable adventurer, if I may say so myself. I suppose you're ready for a more dangerous task. I know a fellow who goes by the name of Lenvell. he occasionally stops by my Inns so be on the lookout for him during your travels. Once you find him, tell him I sent you and he'll know what it's about.
Lenvell will now start to appear in other Inns, in the bedroom. Once you locate him, talk to him and ask about 'A Task'. He will tell you the following:
Well hello there! The Innkeeper mentioned I might could set you on a quest of mystery and fortune did he? Well... yes, that sounds about right. Ah, well let's hop to it then! Rumor has it there is a very valuable ancient skull that was left behind by a long forgotten race of people. Not many know the location of such relics. I, however, came across some information that should lead you directly to the whereabouts of said artifact. The skull is hidden in plain sight, you see. Go to the island located at (The location depends on your game seed) and look for a large rock. The skull is concealed within the rock, but if you are looking for it, you should find it. Once you obtain the skull, bring it back to me and I'll instruct you on what to do next.
Lenvell will direct you to a specific island, where you'll find the Ancient Skull in a special boulder. The boulder in question resembles a normal large boulder, but with a small protrusion on the side. Mining this protrusion will reveal the Ancient Skull.
Upon returning to Lenvell with the skull, he will say the following:
The Ancient Skull
Ah yes! I see you've found the skull. I'm afraid I kept a small detail about the artifact from you. The skull is actually a cursed artifact.
Yes, yes, I know it was wrong of me. But if you only understood the peril the skull can wreck on the world, you would see why it's important that it falls into the right hands! I knew only a person with true bravery and grit could remove the curse. After speaking with the Innkeeper, I determined that you were the right person for the job. I want you to remove the curse.
Throughout the world there are a group of people who still practice dark and ancient magic. They are known as cultists. I've read countless books on such people and they often carry with them tomes that contain information on curses and rituals. According to legend, they can be found worshipping throughout the night at ritual sites. Find these cultists and see if you can obtain some information on how to remove the curse. Once you have the information you need, you'll know what to do.