As some other answers mention, it's easy enough to get a conversation in exchange for a cigarette: just be straight forward "I will trade one cigarette for one conversation". It seems, however, that you want the other person to actually be interested in the conversation, and not treat the conversation as a requirement, chore, or something that can be beaten. If you want the stranger to be interested in a conversation, the onus is on you to be interesting.
There is no general answer to what people find interesting, so you'll have to do some work. Luckily, this stranger, let's call them Jessie, already let you know something they are interested in, your cigarette. So, start with something you know will interest them; immediately agree to give Jessie a cigarette, but also start a further conversation with them. Before actually handing Jessie the cigarette, perhaps while taking it out, ask them questions to try to find something that interest them. After you find something that both you and Jessie are interested in, and exchange a few lines about it, hand them the cigarette, preferably while asking another question. More than likely, Jessie will stay around for a bit. After all, you are in the middle of a conversation that they are interested in.
Of course, this won't always work. Jessie might be in a hurry, or they might exit the conversation as soon as you hand over the cigarette. In particular, if you just can't find anything that seems to interest Jessie in a reasonably amount of time, hand them the cigarette anyway, and let them walk away if they choose to. Don't fret when it doesn't work; you haven't lost anything but a cigarette, which should easily be offset in the long run by the mutually interesting conversations you do have.
Finally, an example of how a (successful) conversation might go:
Jessie: Hey, do you happen to have an extra cigarette?
You: Of course, but humor me for a minute. (Begin taking out cigarette) Have you seen any good movies lately?
Jessie: No, not really.
You: Are you reading any good books?
You: (Holding requested cigarette in hand) Well, are there any bands you like?
Jessie: I'm pretty in to A Perfect Circle.
You: Really? Me too. (While handing cigarette) Are you hyped for the new album? What do you think of the new songs?
Jessie: (Takes cigarette) Yeah, of course. Disillusioned is pretty amazing!
You: Need a light?
You: (While getting out lighter) I really like the influence Puscifer's sound seems to have had on Disillusioned. I think it works really well with the rest of APC's style.