I used a program caled Deluxe Paint to do it back in the late 80s/early 90s. Back then pretty much all pictures used a pallete anyway; it was a matter of creating a static image and just making sure you use a specific range for the parts you want animated. A lot of times it's just highlights you want to sparkle, lights you want to blink, or water you want to shimmer, and you'll create a range (with e.g. a gradient) for those specifically anyway). More complex effects are possible, but can be a bit time-consuming.

[edit] To clarify I did not do the drawings on this page. Also if you want to see a good example of slightly fancier effects than just shimmering, look at the "swamp cathedral - Day" sample there and hit options. See how there is one range that is just for the rippling water, but then a different more complicated range for making the reflection shimmer appropriately; in that one they had to cycle very specific regions from purple to green for the boundary between the reflection of the hill and the reflection of the building.