I have a bit of experience with this.
A project I worked on a year ago was stereoscopic, targeting those special glasses. You basically render out both eyes, composite them separately, and then load them as two separate streams into the player. The player then makes sure the streams are synced and that the correct stream gets shown to the correct eye.
I don’t know if Combustion has any useful features for doing that kind of work… You may end up having to just reconnect footage once composites are done and render out each eye in that way. I believe Toxik has something where you do the comp once but it’s smart enough to know that you have two sets of source footage that need to be rendered, one for each eye. I’m almost positive that Nuke and Fusion both support that workflow.
As far as the AVI format goes, it’s up to the projector and whatever player you’re using. For example, on our project we had to output Indeo 5.0 AVIs. (Yes, you read that correctly.) It’s not a huge deal to recompress for whatever player you use, but I’d get my hands on one of the projectors as soon as I could.
At the moment there are no special plugins or anything-- just two sets of the same footage. I hear they’re adding support for 3D to the H.264 spec, but it’s a ways off yet.
Hope that helps!