Use GrafX 2 (open source 8-bit image editor similar to the old Deluxe Paint) and
watch this video where Mark Ferarri (artist for older LucasArts games) explains in detail his methods. You can also find Deluxe Paint 2 itself somewhere online which has some features that GrafX 2 doesn't yet. Mark actually uses a different tool (which I forget but he names in the video), but it's not free and GrafX 2 will mostly do the same things. Specifically check out the parts where he talks about "clown balloon placeholder colours" (or something similar). Skip to the appropriate sections you need because he stops talking about 8-bit art and colour cycling and starts talking about "8-bittish" art and his work on Thimbleweed Park. He comes back to the topic a couple times, though, so seek through the whole video. Or just watch the whole thing it's quite fascinating.
Basically, you MUST work in an 8-bit environment so that you're using the correct palette entries. Just because they're the same colour doesn't mean they're the same entry, obviously. Creating gradients will be a nightmare otherwise because the gradient colours need to be in a range all in a row next to eachother in the palette. What you do is use placeholder colours that are just off the wall and stand out (like yellow, red, purple, etc) which you can then replace with gradient ranges of your choice. You can do this in GrafX 2 by clicking on the FX tool button and selecting the Stencil option. This allows you to choose a colour that the program will only allow you to edit, ignoring all the other colours. In this way you can select your "clown colours" and replace each one with a gradient.
To select a gradient, go into the palette first of all and define your gradient range by click on one entry and selecting a certain colour, then clicking on another entry a few counts away and selecting your other colour that you want to gradient to, then click and drag (in the palette) the starting entry to the ending entry and click the option "spread". This will create the gradient. Then right click on the "Grad. Rect/Grad. Menu" tool and click+drag to select the rage you just created. This window has a couple extra options like changing the dither style and adding/removing noise to make it look less or more uniform. Different settings give different textures which you get interesting results with depending on what you're trying to do. You can also test the colour cycling with the slider on the bottom which will change the rate of cycle speed so you can get an idea of what it will look like.
The video was invaluable to me for understanding how Mark (and Sierra and other 8-bit artists for that matter) created their beautiful works. He also explains how best to shape and create gradient "blobs" so that they really do grant the illusion of motion and not just shifting colours. He mentions a tool being developed by Joseph Huckaby which would do even more than the tool he uses does. But it hasn't been released yet. I've been following him on Twitter ever since waiting. lol
Hope that's helpful.
