I had a car once that was owned by a smoker. I never did get the smell completely out, but here's what I found worked pretty well.
1. Get rid of all the cigarette ash. It is amazing where it ends up. I completely disassembled the center console (around the shift boot, e-brake, ashtray, etc.) and removed the inside door panels (a lot of smokers flick ash out the window). Check any cracks near the rear package tray, ash blows back and circulates in the back. If you don't get ALL the ash out, you'll never get the smell out.
2. Shampoo (Bistle little green machine, with just hot water, no detergent) the headliner, carpets and seats, use quality leather cleaner if you have leather. Best to do this with the seats removed, which you'll want to do in step 1.
3. Once the ash is out and everything is dry, use one of those ionic air filters (like Sharper Image sells) and let it run overnight with the windows closed (A small crack for the power cord is OK).
That should just about do it. I tried some of the fabric oder remover (Fabreeze) but I think that smelled worse than the smoke.