You could try the cloud effect in the Premiere 6.5 QT FX and reduce opacity on a superimpose track to simulate moving smoke. Fairly crude, but no cruder than using the cloud effect in PhotoShop.
What you really need for smoke is either a video of real smoke, or the sort of particle emitter effect that is available in some software (but not Premiere).