As you say, Katie, I think that the amount of work involved would likely depend heavily on your art style.
In a relatively straightforward realtime-3D art style I could see it being fairly simple, perhaps involving a pair of directional lights (one each of the sun and moon) that change their positions and intensities, along with a good shadow system. Presuming that the shadows were already implemented for more general use I could see a day-night cycle not being a major addition in terms of art.
For some 2D art styles a shader might be conceived to handle the effect: no change in daylight, shifting to a desaturated blue to represent night, perhaps. Look at the lighting used in
CANDLE, for example.
The above is off of the top of my head, however, and may well be missing some complexity.
Other art styles, however, might well call for rather more work, especially if you want significant changes for the various times of day (silver sparkling in the moonlight, or fireflies that come out at night, for example).
I would also like to note if the day-night cycle were to have an impact on gameplay -- such as the player being required to find a place to sleep -- then that would likely call for work in balancing those changes, making sure that the cycle is long enough that the repetition doesn't become tiresome but short enough that it actually does impact the game, making sure that it doesn't adversely affect puzzle-solving (perhaps by interrupting puzzles), etc.
Perhaps a middle ground might be found (in a hypothetical new King's Quest, at least) in having a day-night cycle that progresses as the game progresses, with the game being designed for only limited returning to previous areas, allowing the day-night cycle to be incorporated into the art of a given screen.
As to the original question of whether it might work in King's Quest, I think that I'm going to go with those who said that it depends on whether it adds to the game. For myself, I don't think that it would add to most of them, although I could see it reinforcing the idea of having a limited amount of time in which to work in King's Quest 3. I could see it adding to some new game (as I mentioned above), however.