I just want to make videos like this one:But I can't imagine how to do them. I mean, what kind of software is he using?
This is called a "write on" effect and is typically accomplished with either a 2d animation package such as Adobe Flash or with a motion graphics software package such as Adobe After Effects or Apple Motion.
It generally involves building the imagery as vector graphics. Any lines that will be animated are generally drawn as paths that can be "written on" by starting at the beginning of the path and drawing the line until it reaches the end of the path.
It can also be accomplished using motion recording and a digitizer tablet which will allow the writing to be done in real time and recorded, it can then be accelerated or decelerated as needed, or the paths created and timings can be tweaked to smooth things out using typical keyframe animation.