"Cheese is green on Tuesday" is a text event (not a sign, but it made more sense if there was one) right above the sign explaining how to beat the Queen. To reach it, you need to use the Fly Carrot on the other side of the doors to the left.
Or, if you're thinking "wait, it's not in Dungeon Dilemma", no, they're in Knight Cap now. There was no real reason to separate the two levels in the narrative.