The Urban Legend web-site, Snopes argues that this legend is true.
It is the bodily energy devoted to the digestion of the green stalks that exhausts calories.
They also emphasize that it works as a displacement too:
those who are eating it aren't eating something else
Their references seem to be largely based on newspaper articles, which isn't reassuring. (They also cite Food Reference but they aren't terribly wedded to the claim, prefixing it with "supposedly".)
The Straight Dope tried an ad hoc experiment, showing that even ignoring the cost of digestion, over a period of an hour eating celery, the total calories consumed were outweighed by the base rate of calorie-burning by a person eating (or even resting)
After an hour I'd eaten eight stalks. (I was interrupted a couple times, thankfully.) All things considered, I think I packed away as much of the stringy stuff as could reasonably be expected. Total consumption: 514 grams. Total calories ingested: 72.
Bear in mind that you burn roughly 60 calories per hour while asleep, 85 while eating [...] According to one calorie calculator I found, I need 78 calories per hour just to support my body weight.
So both sites, with limited rigour, suggest that yes, eating celery burns more calories than it provides.