There is no easy way in Premiere.
AfterEffects is the best high-end way to remove shake and jitter, but there is a high learning curve. I would recommend ProDad Mercalli. Go to their website and try the trial. If that doesn't suit your fancy, then invest in AfterEffects.
No, you will need Mercalli from Prodad as a plugin or After Effects.
Invest in a good tripod, saves a lot of bad footage.
Edit: Ah Brian just beat me to it.
If you do decide to go with After Effects, the terminology that you'll be looking for is 'stabilize'. You use the motion tracking features and then After Effects uses the motion tracking information to remove that motion from a layer. Removing camera shake is actually pretty easy, compared with motion tracking tasks that require more precision.
AE CS4 & CS5 also both come with the motion tracker plug in, mocha AE.