We started with two full color video channels (right and left) – anaglyph (the red/blue method) is not ideal, but it is accessible because you don't need a special screen (just special glasses). I'd like to try this with polarization or autostereo some time.
For the anaglyph version, we overlaid the two tracks in a video editor and set the compositing mode to "screen" (also known as "add" in some editors). We removed the red channel from the right, then we removed the blue and green channels from the left.
We also had to adjust the offset a little bit so the "focus" was on one of the middle birds. Whatever the two channels "line up" on will be the "focus," also known as the "screen plane depth." Whatever is in front of that will "pop out" and whatever is behind will "pop in."
The video editor we used was Adobe Premiere CS4, but you can also do this in cheaper / free software. I also tried it in the video sequence editor in Blender and got a favorable result.
The following video shows a slightly different method of removing the color using Final Cut Pro: Make a 3D Movie: 4-Minute Film School.