Plasticine or molding clay would be a great material for something like this. They are not expensive and either would compliment nicely with the wood tools that Robert Cartaino suggests as well. If cared for properly you should be able to put it all away and use it again given that it is a forgiving medium (Assuming you don't want to keep the treasures!).
Playdoh could work as well but the above materials hold there shapes better and would be easier to carve with proper carving tools. In a pinch this would work.
You can also get into other sculpting tools like clean-out or loop tools.
Image from rednebulastudios.com
I wanted to mention those specifically because, even though purchasing them might be costly, there design is rather simple. You can find tutorials on how to make your own. Here is a link to another that makes some simple hand sculpting tools. Kids could find it rather satisfying to carve out chunks to then use in other locations (destruction can be fun!).
Other tools to consider
I found the following video contains a nice introduction of some basic sculpting tools including the loop tool previously mentioned. You could likely find household substitutes for some of these. At least the ones you want your children using.
Pottery Tool Kit Demo on YouTube
These tools are more geared towards sculpting but some of the same techniques will apply to carving.