I don't know how did they do it, but I would do it this way:
.. Okay, so you paint your image in different layers. And if your character has a weapon that covers his body, you have to paint the body under the weapon anyways, because when it will be moving - you will see the body (or blank space if you ignore this).
.. You export you image to a software which allows a still image to be animated. There are few options available. For example, you can use Adobe Flash and rig (make a skeleton) your character and then animate it. Another option - animate the character in compositing software. After Effects is good pick. I believe there was some kind of rigging functions too, but I am not sure. And third option: you pick your favourite 3d application, make orthographic camera, rig the character as you would rig any 3d character. So you rig your 2d planes with the character image as texture, and animate it.
.. Apply effects like flying leaves or dust. You can do particle effects in compositing software (After Effects again) or you can do them in you favourite 3d application. Though you will have to throw those particles into compositing software anyways.