Brief Summary: The goal of this research study is to compare a program called Motivation And Problem-Solving (MAPS) to the standard treatment to help participants with a history of cervical cancer or high-grade cervical dysplasia quit smoking.

Detailed Description: Study Groups: If you agree to take part in this study, you will be randomly assigned to 1 of 2 possible study groups. Randomization means that you are put in a group by chance, like the flip of a coin. A computer program will make this random assignment. * If you are in Group 1, you will receive free self-help materials, and a referral to the Quitline. * If you are in Group 2, you will receive free self-help materials, a referral to the Quitline, and 6 telephone counseling sessions over the next year. The Quitline provides free quit smoking services to eligible callers. No matter which group you are in, you will also receive a 12-week supply of nicotine replacement therapy. The strength of the nicotine patches and lozenges you receive will depend on how much you smoke each day. You should use the nicotine patch as directed by the package instructions. Unused and used patches have enough nicotine to poison children and pets. Be sure to fold the sticky ends together when you are done using the patch. In case of accidental overdose, call your doctor or a poison control center right away. Even if you do not wish to use the nicotine patch, you will still be allowed to take part in the study. Study Questionnaires: You will be asked to complete questionnaires over the phone 5 times: * Baseline * Month 3 * Month 6 * Month 12 * Month 18 You will be asked about your feelings, moods, cervical cancer or dysplasia diagnosis, and smoking status. These calls should take about 45 minutes each time to complete. Saliva Testing: At Months 3, 6, 12 and 18, you may also be asked to provide a saliva sample to test for cotinine to confirm your smoking status. Cotinine is a chemical released in your body when it breaks down nicotine. You will receive a kit in the mail with supplies for testing. The research staff will call you to make sure that you received the kit and to discuss the instructions with you. If you have any questions about how to use the kit, you may contact the study staff during the study. To collect the saliva, you will put a small piece of cotton in your mouth for a few minutes. You will be asked to mail the saliva sample back to the research staff, using a prepaid return envelope. You may be contacted by mail, telephone, and/or email during the study to be given reminders to send back the kit. Telephone Counseling: If you are in Group 2, you will have 6 telephone counseling sessions that may last up to 30 minutes each. These calls will occur over a 12-month period at times that are convenient for you. During the calls, you will be asked about how motivated you are to quit smoking, what barriers to quitting you may have, and factors that may be related to your smoking such as stress and family issues. These sessions will be digitally recorded. The recordings will be used to help the researchers make sure that the counselors are following the correct procedures and to help the investigators better understand or improve the counseling. Length of the Study: Your participation in the study will end when you complete the final questionnaire call at Month 18. If you wish to leave the study early, you should tell the study staff that you want to stop taking part in this research study. Once you tell the study staff that you want to stop participating, you will not receive follow-up questionnaire phone calls. This is an investigational study. The nicotine patch used in this study is FDA approved and commercially available. Up to 455 participants overall will take part in this research study. In-Depth Interviews: If you agree to take part in this study, you be asked to complete a questionnaire and will participate in an in-depth interview. Demographic and Smoking History Questionnaire: At the time of your visit you will be asked to complete a questionnaire in efforts to collect demographic and smoking history information. You may refuse to answer any question that makes you feel uncomfortable. The questionnaire may take up to 10 minutes to complete. In-depth Interview: You will be asked to discuss various parts of a new program designed to help women with cervical cancer quit smoking. You will be asked your thoughts on how important you think the program is, your feelings about it, and if you like it. The interview is designed to be done in a non-threatening, non-judgemental, and supportive way. The interview should last about 2 hours. In-depth interviews will be audio recorded and transcribed (written down). Your participation in this study will be over when you complete the interview. This is an investigational study. Up to 30 women will take part in the interviews. Up to 350 participants overall will take part in this research study. All will be enrolled at the Stephenson Cancer Center.