How to make such an animation?

For some designs, you can start in Illustrator, blend paths, expand the blend, release to layers, then import as a comp and sequence the layers to produce fancy shape morphing animations. It can be a lot easier than hand animating paths for some designs. That would be one way to create the animating leaf part of this sample. 

Here's a very quick tutorial I did a long time ago on morph shapes using Illustrator workflow. Maybe it will give you some ideas.

My YouTube Quick Tips

There is no simple answer to your question. Clearly this is elaborate path animation and that takes practice, practice, practice. Plug-ins and expressions may have been involved to create the soft bounces and delays, but overall this is simply an experienced animator putting his skills to use. It's really not a question of "Where can I find a tutorial?" or "What tools have they used?" if you were hoping for that. Point in case: You just have to do it and crank out project after project until you have worked up enough experience to understand keyframe timing and all that. This would not be different with the Puppet tool or whatever. there are no easy answers here.

Mylenium