How about a Federally-mandated cap on the amount of nicotine allowed in cigarettes? If x ppm is the current standard in 2008, reduce the cap to 90% of x ppm by 2010, 80% by 2011, …, 10% by 2018, and 0% by 2019. By then people will have no chemical addiction that causes them to smoke.
Of course, combine this with an increasing tax on cigarettes, so that if y is the current tax per stick, double that to 2y by 2010, triple that to 3y by 2011, and finally 10y by 2018.
This double plan will make smoking increasingly undesirable by making the cost of doing so prohibitively high while the benefits nearly null. Smoking costs the world an immense amount of money in lost productivity and costs associated with bad health. This would be a good way to end the problem.