Seeing how smoking cigarettes went from being popular to being rare in a lots of places I would say:

1 - make it uncool (no more james bond smoking in cinemas, packaging that reminds of diseases)

2 - make it expensive (tax the hell out of it)

3 - make it a hassle (no smoking in closed spaces, airplanes, universities etc)

The thing is, both weed and social networks became popular right about when smoking stopped being popular. So maybe there is an extra step, a perverse one:

4 - provide a substitute addiction.