We're buying a house from previous owners that were smokers. The house still smells of smoke even with no furniture or upholstery in it. We plan to replace all the carpet with wood flooring. We're hoping that will do the trick. But our realtor indicated that it might also need to be repainted and possibly primed with something like Kilz too. I'm just trying to get an idea of what we're in for.
I know you're removing the carpets, but shampooing them will get rid of a lot of the lingering smell. You may need to do it more than once; if so, make sure to let them dry completely in between. After they're dry, vacuum them with a HEPA filter to remove dust or smoke particles that you might have dislodged while shampooing.
Smoke will have settled on all the surfaces in the house, so you should definitely think about repainting the walls and ceilings. Clean them thoroughly first using TSP. The Kilz that your realtor recommends is both a sealer and a primer; it will seal in any stains and smells and provide a good base to paint on.
Other surfaces should be cleaned too: kitchen or bathroom floors, doors, windows, countertops, etc.
Finally, just airing the house out will help some: open all the windows and have fans pulling fresh air into the house. You'll need good ventilation while painting, so you should be doing a lot of this anyway.