Completely remove nicotine stains and odors from walls?
For walls you definitely want to wash with HOT water and a hefty mix if tri-sodium phosphate (TSP). Make sure to wear good rubber work gloves that cover some of your arms as well. TSP exposure can be quite hard in the skin of your hands. It can also be helpful to rinse after the wash with a clear wash of warm water. This is necessary because the smoking deposits on the wall are not a good candidate for paint adhesion. TSP on the other hand actually will take some of the gloss on old paint layer making an improved surface to which to apply a primer.

I reclaimed a house from a very heavy smoker family and had to also remove all the popcorn textured ceiling material. It had to be scraped off to the bare ceiling drywall. Then the ceiling needed to be sealed with a clear sealer material to seal in stains and the odors that had worked their way up into the drywall. 

In my case the smoking smell had even permeated up into the attic space and the insulation up there. I had to install a gable end attic fan that I let run continuously for months to reduce the smell of the insulation.