Suppose that I would like to record some video sessions of Angry Birds on my phone.
Are there any apps that I can use? I have root permissions.
I just read a review of Screen Cast & Screen Recorder that's pretty compelling. It requires root, like any on-device solution I'm aware of, but can record decent quality video at up to 30 FPS. The review has example captures from various games and the videos are good enough for most anything you'd want, unless you need HD video for some reason. The app has a free trial so I definitely recommend trying it out.
Yes you can, even without root, by using adb, ddms, and DroidEx. See: http://answers.oreilly.com/topic/951-how-to-capture-video-of-the-screen-on-android/
The basic idea is to use ddms to capture a screenshot rapidly, and then composing these screenshots into videos.
I haven't actually tried this yet, so I don't know how well it works (or whether it works).
I doubt this can be done practically purely in device-side; problem being that video is extremely memory heavy without compression, and compressing video in real time will be a torture to even the latest phone's CPU.
Airdroid has a "Record Screen" option. It's not a premium feature and doesn't require root. It records the screen along your microphone (warning! As far as I remember this option is set by default!) if you do like to make tutorial videos.