Video editor w/ stabilization?

Cinelerra is the only tool I'm aware of that can do this in Linux. There is a tutorial on just this topic.

Be sure to check out MLT and it's videostab2 filter.