Ah, yes.
Shadowgate. I remember this game well. While
WWWWolf's solution above works, this is a classic case of using
brute force methodology to solve a problem when there is a much more
elegant solution available.
A bit earlier in the castle, you find another puzzle - the Sphinx. The sphinx refuses to let you up the stairs in the room he sits in until you provide him with an item that answers his riddle; either a mirror, a bellows, a broom, a map, a skull, or a horseshoe. Once you solve the puzzle with the appropriate item, don't go dashing up the stairs just yet. If you do, you'll end up stuck at the levers. Take a moment, and look closely at the stairs. More specifically, look closely at the scratches on the stairs. Take note that there are three stairs, each with three scratches.
Yes, it's true. The solution to the Lever Puzzle is scratched into the staircase in the room with the sphinx, just a few rooms away from the puzzle itself, and it's the same each time you play. If you'd like to just know what it is, the solution is here.
Speaking of sadistic game designers, take note that the solution is the fourth to last one that would be tried using the method above, just enough to prevent someone from jumping to the end in frustration, and solving it that way.