Can I (easily) add text to a movie?
As of 2.76, we now have a text tool in the VSE. See 3pointedit's answer.

Pre 2.76 Answer

(Also for more advanced control over the text)

First, make sure you're in the Blender Internal Renderer.


Then add a text object, and change the font settings to your liking.



Then add a new material, set the color to your liking, and set it to shadeless (this can be changed, but a lot of the time, this is basically what is wanted).



In the Properties panel (N), switch the shading from Multitexture, to GLSL.



Then make sure that your camera is aligned properly, and that in the shading settings, alpha is set to transparent.



In the VSE, add a scene clip, and choose your scene. 



Then change the Blend mode to Alpha Over.

Then in the N Panel of the viewer, set the render type to textured.



In the viewer, you'll notice that the text isn't aliased properly, but when the text is rendered, it should render correctly, but if it doesn't, rendering at double the resolution and then down grading should fix the issue.