What most naturally follows?

How to fix nicotine stained teeth
Use a whitening toothpaste.
Head to the drugstore and look for a toothpaste that specifically advertises whitening properties. These toothpastes can lessen the appearance of surface stains, such as those caused by smoking.
Often, they contain chemicals that break down the stains. Ask your dentist for his recommended brand.