You’ll trigger this quest by completing one of the more difficult tasks in Stardew Valley: reaching the lowest level of the Mines. Filled with baddies of all sorts, not to mention way too many freaking rocks you need to bust open, the Mines in and of themselves represent a significant - if profitable - challenge. You can find more information about getting through the Mines in this article, though here are some general tips:
  • Bring food. You’ll find restorative items occasionally, but not often enough.
  • Upgrade your equipment. The deeper you get, the harder the enemies become. The Adventurer’s Guild has you covered on that front.
  • Upgrade your Pickaxe. You’ll use lots of Energy in the Mines. The faster you can chew through rocks, the better.
  • Complete the Mines five levels at a time. You can risk more than that in a single day, but the chances of dying and losing a bunch of progress rises the more time you spend in the Mines.
  • Do it in Winter. There are no crops to tend to during this season, leaving you more time to explore before bed each night.
The Skull Key is located on level 120 of the Mines, the lowest floor. Opening the chest containing the Key will trigger this quest - now you just have to figure out what to do with it.

Fortunately, the purpose of the Skull Key is much easier to discover than finding it in the first place. Head to the Stardrop Saloon in Pelican Town and look in the room on the right. There are two arcade machines. The orange one contains a game you can play at any time; the blue one is, normally, locked. Approaching it with the Skull Key in your inventory will allow you to play Junimo Kart.

Junimo Kart

First off: I hate this game. So much.

Junimo Kart is a fairly simple side-scrolling, mine cart hopping game. Your goal is to guide a Junimo safely across a series of decidedly unsafe mine tracks. There are two different modes, both of which I have yet to fully explore. (Endless Mode, I think, is just competing for high score.) No clue what you get out of this game as of this writing, because I’m honestly not very good at Junimo Kart.

Need some tips? Have some tips:
  • You can hop fairly high in your little cart. If you only tap the button a little bit, though, you’ll hop just a little bit. Judge the strength of your jumps wisely.
  • There are occasional roadblocks that will kill your little dude - but only if you hit them from the front. if you land on the roadblock you’ll survive.
  • Jumping is not always wise. There are plenty of small gaps where you can simply fall and land safely. If you can do this without risking your neck, I highly advise simply falling from a higher track to a lower track. The less you have to jump, the better.
  • Because the tracks are randomly generated you may get put into impossible situations from time to time. If this is the case, just… die. You’ll be put a little ways ahead, out of said impossible situation.

Skull Cavern

Done with the Skull Key? Not quite. In addition to unlocking Junimo Kart, the Skull Key also allows you to access a new dungeon, this in Calico Desert. In order to unlock Calico Desert you need to either complete the Vault golden scroll at the Community Center or purchase the Bus development at Joja Mart, assuming you've purchased a Membership. Both require 40,000+ gold to complete, and they will both repair the bus at the Bus Stop to the east of your farm.

Head to Calico Desert between 10 am and 5 pm, then head northwest, past a small oasis, until you find a cave. There's a door with a skull face inside the cave. You can open the door with the Skull Key, unlocking the Skull Cavern and completing the quest.