That particular video looks to me like it has a good deal of cel-shaded 3D animation.
Beyond technique, though, I think that the keys to this style of animation are threefold: a very strong sense of graphic design for each tableau; deep, richly layered textures; and well-thought out transitions to seamlessly link each scene.
Walter Soyka
Principal & Designer at
Keen Live
Motion Graphics, Widescreen Events, Presentation Design, and Consulting
RenderBreak Blog - What I'm thinking when my workstation's thinking
Creative Cow Forum Host: Live & Stage Events