Must Have Nicotine

Mary: Excuse me--you don't have a cigarette on you, do you?
Tiffany: I'm sorry. I don't smoke. It's not that I worry about lung cancer, but it does stain your teeth.
Mary: Well, I worry terribly about lung cancer. I also worry about shortness of breath and heart disease. But what really worries me right this minute is that I'm not going to find a cigarette.

—Mary, Mary

"If I don't smoke there's gonna be secondhand bullets coming your way, lady."

—Bill Hicks

Tobacco smoking is addictive. Therefore, characters who smoke will sometimes find themselves in scenes where they are desperately searching for a cigarette, or a means to light it, or (more recently) a place where they can light up.

Goes hand in hand with Cigarette of Anxiety. Compare Must Have Caffeine. Beware Nailed to the Wagon.

Examples of Must Have Nicotine include:

Anime and Manga

Fee in Planetes has this. To an epic extent.
The Ichigo Mashimaro manga had a chapter which involved Nobue attempting to give up smoking. She subsituted it for Pocky. After she realized she was gaining weight, she went back to smoking.
Futaba Kun Change had a lingerie salesclerk so addicted to smoking that the white undies in her area had turned yellowish. She later sneaks off for a smoke break and accidentally sets the store on fire.
Fujisawa-sensei from El-Hazard: The Magnificent World. Earlier it's discovered he has Super Strength when he doesn't drink alcohol. It's discovered he's even stronger when he doesn't smoke either.
Kaiji: Kaiji reaches for his Marlboros in the restroom during the break of the E-Card match, but realizes the smell could raise suspicions and screw his plan.
There's an episode in Gintama in which tobacco is banned in Edo. The effects on Hijikata are... unpleasant.
Badou of DOGS Bullets and Carnage is a generally somewhat useless and good-humoured one-eyed chain-smoking PI with bad luck, but when deprived of a smoke for about three minutes at a time he goes Axe Crazy and becomes completely unstoppable in search of a smoke/punishing the reason he doesn't have a smoke. Several antagonists deny his last request for a puff and never do anything ever again. He takes this problem of his in stride. So do all his friends, except when he trashes their bar. It seems to be viewed in-universe as a sort of (kind of stupid) special ability. Is played for drama and comedy at the same time. The eponymous carnage helps here.
Sasamoto-sensei in GA Geijutsuka Art Design Class looks completely miserable when she hadn't smoked for two hours. There's a reason why she usually avoids working in the faculty room, or told Usami-sensei that she doesn't mind paying Usami to buy her a carton or cigarettes.

Comic Books

Spider Jerusalem in Transmetropolitan.
John Constantine in Hellblazer. This is a man who went to the trouble of Out Gambitting three incredibly powerful demons so he could be free of his lung-cancer...and then kept chain smoking.

Fan Works

Naruto the Abridged Comedy Spoof Series Show depicts Naruto as a chain smoker who does everything for his next cigarette.

Film

Dr. Grace Augustine in Avatar. Her very first line?

"Who's got my goddamned cigarette?"

Literature

Seems to happen a lot in Catherine Alliott's The Old-Girl Network.
Discworld wizards sometimes get like this, most notably Igneous Cutwell in Mort:

What Cutwell wanted was what any normal wizard wanted at a time like this, which was a smoke. He'd have killed for a cigar, and would have gone as far as a flesh wound for a squashed dog-end.

The Lord of the Rings: Gandalf gets increasingly irritable in Moria, since he doesn't dare to smoke there in fear that the resident orcs might catch a whiff. He finally caves in the last night of the underground journey, after Pippin already had dropped a rock in the well, presumably figuring that damage had already been done.
One of P. G. Wodehouse's Mr Mulliner short stories is about a young man who quits smoking because he is under the misguided perception that it is what stops the girl he's in love with to fully accept him. It doesn't take many hours for him to go insane with the urge for a smoke. Hilarity Ensues.
In the Ryanverse novels by Tom Clancy, former smoker Jack Ryan frequently has cigarette cravings when he is feeling stressed.

Live-Action TV

Played for drama in an episode of Grange Hill (circa the early 2000s). The science teacher, who spent most of the series rallying against smoking, being tormented by one student and misblaming another (who was actively being framed) is trapped under debris with both of these students. He's stopped from a relapse (indicating how stressed he is) by the latter student, who smells a gas leak.
Very much played for comedy with Chandler in Friends, who has officially given up smoking prior to the series beginning, but keeps relapsing and trying to stop the others finding out.
Bill McNeil on News Radio had to quit cigarettes, so Dave promises to give up coffee along with him. Neither takes it very well.
This is the plot of one episode of (rather predictably) The Smoking Room, where nobody can find a working lighter. Finally, someone finds a matchbook with a single match left... and then Hilarity Ensues.
Used in the second series of The IT Crowd - Jen, an ex-smoker, is driven to this when Denholm, in his funeral video, wrongly attributes his death to lovely, delicious fags. She fishes a cigarette out of the gutter outside the church and happily puffs away.
- Taken even further later in the series when Jen and her smoking co-workers are forced by their habit to undertake a grueling march through Siberia to the smoking shed.
Capt. Sig starts feeling mysterious chest pains and, knowing that his family has a history of heart problems, decides to quit smoking for a while. The other crew members are incredulous, and sure enough Sig grabs a cig about an hour later.
Shane Powers (Exile Island, season 12) decided to use Survivor as his personal detox and quit a month before filming began. Like the NCIS team without their joe.
On Burn Notice, Michael's mother is rarely seen not smoking.
Sherlock: Sherlock Holmes is seen wearing not one, but three nicotine patches while trying to figure out a case and lamenting how impossible it is to maintain a smoking habit in London. Well, it's better than the cocaine Holmes took in the novel.
Becker: Dr John Becker. Many episodes deal with him trying to quit. When he doesn't have his cigs, he's even more of a Dr. Jerk than usual.

Music

The subject of the song "Smoke! Smoke! Smoke! (That Cigarette)", originally by Merle Travis and Tex Williams (and later covered by many other artists):

Smoke! Smoke! Smoke! that cigarette.
Puff! Puff! Puff!
And if you smoke yourself to death,
Tell Saint Peter at the golden gate,
That you hates to make him wait,
But you gotta have another cigarette.

New Media

Parodied, like everything else, in The Onion. One article says that the United States has banned smoking except in a basement closet in a building somewhere in the Midwest. Naturally, the millions of American smokers, rather than quitting, spend in upwards of six months driving cross-country just for a single cigarette.

Newspaper Comics

One short arc of Bloom County had Binkley's father going through withdrawal when Binkley hides his cigarettes. Collected in Penguin Dreams and Stranger Things (1985).
- There's a much more epic arc when Steve Dallas is forced to quit.
Alex has frequent strips about the 'smokers clubs' that gather outside buildings where smoking has been banned. One featured the heaviest smoker in the building signing a petition to get smoking banned, hoping this would encourage him to quit. Instead, he ended up becoming much fitter due to his frequent trips up and down the stairs so he could smoke.
Dick Tracy's partner Sam Catchem is rarely seen without a puff of cigarette smoke emanating from his head. His smoking habit has now long survived Ben Grimm's cigar and Commissioner Gordon's pipe, demonstrating one hell of a Grandfather Clause.

Theatre

In the third act of Mary, Mary, Mary starts hunting around her ex-husband Bob's apartment for a cigarette. He enters and soon joins the desperate search for cigarettes, and finally discovers some under a chair cushion. (According to her, he smokes only one pack a day, implying that she's a heavier smoker.)

Video Games

Metal Gear Solid
- Solid Snake only really counts by the fact he went to extremes to get his nicotine fix while on Shadow Moses Island (he swallowed the pack and well... somehow got it out of his stomach). Talk about a devoted addict!
  - He also gets points for the cutscene where he first meets Naomi in Metal Gear Solid 4. He's constantly trying to light it, fumbling it, dropping it, having to find it again, failing to light it, having it stolen by Naomi, and so on and so forth, for the whole scene, and Naomi doesn't even pause expositing at him about how he's going to die, horribly.
- In Peace Walker, Big Boss gets locked in a cell for a relatively short time - not more than a day or so. As soon as he's freed, he starts coughing and complaining that his 'lungs taste like charcoal' from how little smoking he's been doing. Thing is, Big Boss smokes cigars.
- An actual plot element with another character in Peace Walker, who has a cute tic of placing her forefinger onto her upper lip. It's revealed that this because she's actually a heavy smoker, but can't risk doing it for fear of revealing who she really is, and so has resorted to tucking a parcel of snuff under her top lip to absorb it through her gums. Since she's not used to it, she keeps fiddling with her upper lip to keep it in place.
Deja Vu 2: Carrying around the empty pack of cigarettes will have the game narrator mention how you crave nicotine and want a cigarette, but cannot due to lack of cigarettes.

Web Comics

McCoy from Mushroom Go.

"Do you see this cigarette? I pulled this cigarette out of a dead guy's pocket. It's not even a brand I like. I smoke Reznor Reds, and this-- trust me-- is no Reznor Red. But I'm going to smoke it anyway, and you, you big jackass, you have what may well be the only lighter in this entire stupid building. Not just any lighter, but my lighter. Now, one way or another, I am going to smoke this cigarette and I am going to enjoy every awful second of it."

Maxine in Broken Plot Device, in contrast to Liz's coffee habit.
The titular character of Jix starts shaking when she doesn't have access to nicotine, though she tries to quit a few times (until her alt-personality Remula accidentally smokes a pack).

Western Animation

Pinky and The Brain: The Brain had this problem in one episode. Pinky sums up the trope very nicely:

Pinky: This O'Tine fella must be really clever if he can get people to suck burning stinky leaf-gas down their throats.

The Venture Brothers: In one flashback, Molotov Cocktease ties Brock to a bed and then sets the room on fire. But what really pisses him off is that she took all the cigarettes.
The Classic Disney Short No Smoking has Goofy giving up smoking. A minute later, he's running all over town, desperately looking for a smoke.
An episode of Ozzy and Drix had Hector starting smoking a few puffs in a wrong crowd. All of the blood cells except for cold pill Drix are mind controlled demanding nicotine.
Done in an episode of King of the Hill where Bobby and Hank take up smoking where when at school and work respectively everything around them reminds them of cigarettes.
Bender of Futurama enjoys cigars on a regular basis. In "Three Hundred Big Boys", he uses his tax refund to buy burglar tools—in order to steal a $10,000 cigar. It so expensive because it was rolled by Queen Elizabeth II using part of the original US Constitution.
Lisa Simpson from The Simpsons gets hooked by passive smoking when she dances at the recital. Homer takes all the cigarettes; this causes dancers to smoke other things.