I use ProMotion from Cosmigo.
It allows use of multiple palettes (per frame, per layer), but I always use just one for each file.
Difficulty depends on what effect you are trying to pull off.
The base for the belts is just to repeat a basic pattern with different colors... then cycle them and see what happens.
Some other effects can be a real headache...

Yes, the gear teeth are done with color cycling. That's why the two don't actually touch. The border is a series of curved ramps.

Sadly no good tutorials.
But there is this GDC 2016 talk where Mark Ferrari explains a couple of ways he used to apply it. Starts around minute 49, though I recomend the whole thing. https://www.youtube.com/watch?v=aMcJ1Jvtef0

Ok, to clear things out. All the animations here are hand crafted.

It´s color cycling, a technique from the 80s. You have to place pixels in order so when the colors on the palette shift, they give the illusion of movement.
As a reference, look up Mark Ferarri, he created awesome stuff with this method.

Thanks!
Now I'm wondering, which part of the background seems to you like an effect or not hand pixeled?
Ground, buildings or sky?
 

Thanks! For color cycling I used Cosmigo ProMotion NG.