Can the same thing be done for videos?
Sure, people do it all the time. It's just a matter of choosing the right export format, i.e. one that supports Alpha channels (Quicktime Animation and PNG, TIFF; TGA; PSD;PNG image sequences etc.). Read up in the help.
Oh my god! Finally! I was able to do this. I've been trying to figure this out for SO long now. So Mylenium is right in that you need to use Alpha channels, but I'll explain more fully for people who also have this problem and hate the "read help page" type of "help".
When you're exporting your video, choose AVI and then in the codec settings area, make sure to switch it from RGB to RGB+Alpha.
The part that really threw me off was that I am used to photoshop where it tells me that the background is transparent by using little alternating grey/white squares. So I was looking for something like that to appear in After Effects to tell me explicitly which parts will remain trasnparent, and which won't. However, at least from what I can tell, there is no such thing in After Effects. That initial background you create when you make your sequence, THAT's the part that will be transparent. I hope this helps.
Actually, there is a Toggle Transparency Grid button at the bottom of the Composition Panel that will allow you to see the checkerboard in areas that are transparent.