Avid Free DV - Avid Free DV, poor cousin of Avid Xpress Pro, has all the basic video and audio editing features and allow you to put video in two tracks simultaneously. They have an extensive collection of tutorials online to help you get started quickly.
Support both Mac OS and Windows XP platform. Infact, you can even play with keyframes for generating custom moves and transitions. Ships with the Avid Title tool.
Jumpcut.com - Jumpcut is a web based video editing software and now it's even part of the Yahoo! family. You upload a video or small clips just like importing inside a desktop software.
There are dozens of transitions and special effects. You can import photographs from your Flickr or Facebook account to mix them with the videos. The jumpcut editor is intuitive enough and there is good title support as well. And your movies are published online automatically. Perfect for quick vlogging and video podcasting.
JahShaka* (discontinued) - An open source video editing software that is currently in Alpha stage but has features found only in expensive video editing software suites.
Works on Mac, Linux and Windows. The interface might take some time for you to get started otherwise the software is definitely the most powerful one out there. And the price is just right. $0. Also does 3D effects which you won't find in other free video editors.