I assume that the characters will be moving around a lot. Clay is an option but will deform and require constant resculpting and clean up. I recommend that you sculpt the puppets with foam over the armature and and make fabric clothes. The heads could be made with a core of balsa or foam and coated with a bakeable clay. The mouths can be oil based clay. The hands can also be made of clay or built up with foam and latex. But  I would sculpt a generic pair of hands and make a plaster mould and slip cast several sets

I'm just assuming that you have limited funds, thats where the build up method is ideal. If money and technical facilities are no problem, foam latex casting is the way to go, but is not without its own problems. I have recently made a test with Sculpy Flex and Found that after it was baked it proved to stiff to be of any use to animation, particularly with hands. There are other techniques. One I have used in the past is producing silicone rubber casts from plaster moulds. The home handyman silicone at the local hardware store can even be used for this perpose.

Yeh, foam rubber casting can be a hit or miss affair even to the most experienced technicians. There are always problems with air pockets and shrinkage etc. It is rare to have 100% results on the first foam run.