The maker of that video uses:
Poser 7 - Rendering, Animating, Rigging
Director MX - Compositing
Maya - Modeling
Particle Illusion - Particle effects
Adobe Premiere - Timeline, Syncing final output
Xnview - Image Conversion
I don't know how to use 90% of programs so I'm not someone to go to for tutorials, I use paper, maya, 3ds max, photoshop etc to make stuff, so just mess around with those programs, most are pretty straight forward, find online tutorials for the basics of the programs (no one knows how to use them until the creator teaches someone, or someone figures it out)
In the end, artistic ability is a huge plus, dealing with camera angles, composition, story etc., your work will turn out if you work hard, and patience is key
Thats all i can think of now, i have annoying talking people who never shutup nearby (headache)