How are traditional animated matte paintings made?
While I'm not aware of the process used for that particular film, one easy way to do it is to film the matte painting, then film the smoke against a green or blue background and composite the smoke over the footage of the matte painting in the computer.

I've also seen matte paintings where a large section is left unpainted. Then live action (or animated) things are filmed which exactly fill in the unpainted area. You could composite them either in the analog realm (by projecting both pieces of footage onto the same screen and filming that), or digitally by using compositing software.