Android - Is it possible record videos of my screen?

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.