Hands down for me, and I've tried all. Warp stabilizer in AE. The best because it can correct rolling shutter issues.
You can rent it monthly so it doesn't cost anything in the slow winter months, and i got an email saying it was going down to $30/ month.
It's also the most intense, in terms of computer power required, and skills needed to use it to its full potential.
New Premiere Pro cs6 doesn't require After effects for warp stabilizer plugin. You can download 30 day trial from adobe dot com.
They have also a rolling shutter removal plugin there.
Depends on how long the clip is and how much movement. Sometimes just to get one bad section to be as smooth as the rest the whole thing has to be zoomed in.
Try setting it on Stabilize, Synthesize edges, under Borders, then crank up the Edge feather and Synthesis input range, under advanced options.
But if your video is really bad then... what redridinghood said.
We use Apple's Motion which at £35 in the UK is good value considering the stabilization/smoothing is just one of many features. Only for Mac users though.