I am only running linux, currently Ubuntu 9.04 soon to upgrade to 9.10. I have mixed experiences with video editing software in linux, mainly due to lack of functionality and at times stability. I tried to upload an article with tons of links, but it wouldn't allow me to do that, so it is on my own site instead.
avidemux
The first thing I started using was avidemux, I used it primarily to edit video footage,,,which it is quite good for...its strength is that it is quite stable. The effects are though quite poor (so I supplied that with LIVES), the graphical-user-interface is overly complicated and there are far too many options when it comes to rendering, it is not a Non-linear video editor. Up-to-date versions for ubuntu and debian systems can be downloaded from www.getdeb.net
Lives
Lives can all that most decent video editors can, it just feels really complicated. It has tons of options and a lot of effects and has several graphical-user-interfaces depending on the task you are doing. One of which is a Non-linear video editor. It just isn't for the faint hearted. The fact that it is originally a VJ tool and it is probably ideal for that, is probably also why an average user might be scared of it. Up-to-date versions for ubuntu and debian systems can be downloaded from www.getdeb.net
pitivi
Pitivi is a simple video editor, great for editing your video, it just doesn't have the effects. It has an import from web-cam feature and is a Non-linear video editor. It is also very stable and expandable with plug-ins, there just haven't been any made yet. It is also advertised on the site as being perfect for batch editing, as it can be controlled from the commandline. The version of pitivi in the ubuntu repositories (jaunty 9.04) is v0.11.3 and their current version is 0.13.3. For latest version for ubuntu/debian choose experimental from their downloads page. You can also build from source.
Kino
Kino is a program that I have used a few times. It is not a Non-linear video editor, it is very stable and has a basic set of video effects. It can capture and import direct from the camera. The downside is according to me the graphical-user-interface.
Up-to-date versions for ubuntu and debian systems can be downloaded from www.getdeb.net
Kdenlive
I have probably had my most experience and best experience running Kdenlive. Kdenlive is a non-linear video editor, which has a lot of features, effects, wipes, titles etc... It is probably the best contender for the most complete video editor in linux. It is also greatly expandable, as of date, rendering profiles, wipes and MLT profiles can be user submitted. Kdenlive is easy to use, but with a lot of options, the amount of options can make the menus look bloated in places and it has the bad habit of crashing, so I have to save my projects constantly. Do not use the version of Kdenlive in the ubuntu repositories (0.7.3), rather download the latest and greatest from the kdenlive downloads page, currently (0.7.5). As the (0.7.3) version is very crash happy.
Open shot video editor
The Open shot video editor is fast biting in the heels of kdenlive.It is a non-linear video editor which after only being out since april 2008, the editor has had an explosion of features. The graphical-user-interface is simple and easy to use, a lot of things can be done simply using drag and drop and the effects buttons are made in such a way to show what they do. Even the rendering options are not cluttered. It is also a project that can see its limitations in the eye, therefore it uses inkscape for when doing advanced titles. As of yet it is still unstable when doing some tasks, it also lacks translations and a complete set of features and options. But at the rate at which it is being developed, this wont be a problem soon.
You can get the latest version of Open Shot by downloading it from their main web page or continuously by adding the PPA to your software sources.
Gimp
I have though used the features of gimp to add effects and create animations for videos. It is done through layers, one layer=a frame then you can either make it into an animated gif, as several jpg images or export it into a video using the GIMP Animation plugin. The gimp animation plugin is also great for splitting all the frames into individual images, so you can paint/animate on them, add effects, clean the video for un-attractive elements, remove elements etc. The list is endless. It is also great for making short title animations and the like.
Cinelerra/Blender/jashakka
I have never had any luck downloading or using Cinelerra, so I can't comment on that. Neither have I used the video editing features of Blender. jashakka the effects program with 3d capabilities is also foreign to me, but I hope to use it, as the stuff done on it looks cool. Just waiting for a new version of it for linux, until now I have only gotten it to work on windows.
One of the great advantage when using linux for anything is that the web is full of user generated solutions in the form of screencasts, podcasts, videocasts, faq's, documentation, forum articles etc... So getting started is easy. I have seen that type of content for all of the above on-line.
A good place to start is the wikipedia article about video editing software.