It really depends on what you do with the foam. If you're using it on the interior to give the puppet form and body, the generic foam from Jo-Ann fabrics works like a charm. I used it for the puppet in my avitar, whose body I reconstructed a year ago, and it's held up fine.
If you're gonna keep the foam naked on the outside of the puppet, it won't last so long, simply because it's more exposed to the elements. It also has a tendency to distort in color. If you were to spray paint the foam it would decrease it's life span even more because the paint hards the foam so when you try to bend it, it rubs the paint off -- it's just a mess. So I recommend, if you're exposing the foam, to dye in before you start cutting on it, assuming you want it colored.
The foam that work for me in regard to sculpting was purchased at an appholstry shop. I don't know if it was "Scott foam" or not (that's what the Muppets use), but it was just a big 2 X 2 block of foam. It worked for me!
Also, when you start making your first cuts, be sure to make them with an electric knife (the king used for cutting turkey). It shaves of a much finer layer than scissors will to give you the basic shape you need to work with.
Hope I've been helpful and not too confusing.
--"Scary" Larry Wolf