I want to make a video similar to this one, which includes a lot of animation and text (click to view):
But what software would you use for this? Would Illustrator + After Effects be enough?
If you already ask like this:
Yes, Illustrator is a great tool to generate vector art, and After Effecs can be used to generate animations using vector graphics. In fact, I think After Effects is the most popular animation tool these days for two-dimensional editing. For 3D animation, Blender comes to mind.
For getting into animation, you will need to read up and get to know the software. The internet has plenty of tutorials, like this one, which shows you how to animate a character.
Synfig could be the right tool for you http://www.synfig.org/cms/ There's a Mac version on the downloads page.