Under a Red Moon
Travel to the southern side of Washa's Bluff, south of Tabantha Bridge Stable. You will see a large mushroom-shaped column with a hut, and Kass playing the accordion on top of it.
Speak with Kass and he will point out the pedestal beneath the column while singing a verse about its puzzle. The solution to the Shrine has to deal with the blood moon that happens once in a while.
To force a Blood Moon to happen (or more accurately, in order to wait for one to happen without driving yourself crazy), you can go to Dueling Peaks Stable. One of the NPCs there, Hino, can predict when Blood Moons are about to happen. Ask him about "tonight's moon", and if he says anything other than "I'm getting that feeling again...", sit by the campfire and wait for the next day's noon.
Note: A Blood Moon must happen once every eight days. So don't get discouraged. Before the eight day cycle has ended, you will see a Blood Moon.
Once Hino says that he's getting a feeling about a Blood Moon happening tonight, return to where Kass is as quickly as you can. Set up a campfire or just chill out until night falls.
Once you see the blood moon rise above the horizon, take off all of your armor and stand in your underwear on top of the platform. This will solve the puzzle and the Mijah Rokee Shrine will appear nearby, completing this Shrine Quest.