Seamlessly tiled, scrolling, animated backgrounds

[melody]

This can be seen in the Kirby games, and also on some guy's avatar that I found when I was browsing The Spriter's Resource. I don't know how to animate something like that. I think there's some trick to it that I'm not understanding. I need to know how to do this for a game I'm working on that draws some aesthetic influence from Mischief Makers and stuff like that.

Here are some examples.




I've found some tutorials on how to create a perfectly tiled image, but animating it is another story. Any ideas?