This is a regular Internet meme/joke posted by timewasters on Yahoo! Answers, but it's actually a nice paradox of the "I always lie" flavour. One resolution, which ought to be on a FAQ somewhere, is well-known; but I'd never actually bothered to verify it. The get-out is that Pinocchio's nose grows not merely when he lies, but also when he's stressed.
See the English translation of Carlo Collodi's 1883 Adventures of Pinocchio (Gutenberg EText-No. 500), where there are scenes showing that the nose grows during his presumably stressful creation ...
After the eyes, Geppetto made the nose, which began to stretch as soon as finished. It stretched and stretched and stretched till it became so long, it seemed endless.
Poor Geppetto kept cutting it and cutting it, but the more he cut, the longer grew that impertinent nose. In despair he let it alone.
... and when Pinocchio, first experiencing hunger, is disappointed to find that a cooking pot is just a trompe-l'œil:
A boy's appetite grows very fast, and in a few moments the queer, empty feeling had become hunger, and the hunger grew bigger and bigger, until soon he was as ravenous as a bear.
Poor Pinocchio ran to the fireplace where the pot was boiling and stretched out his hand to take the cover off, but to his amazement the pot was only painted! Think how he felt! His long nose became at least two inches longer.
We might expect, then, that creating a logical paradox will be stressful to Pinocchio, and his nose will grow. This is the standard resolution, though I guess that doesn't solve the problem entirely; what if he practised relaxation exercises to the point where he could confront the paradox calmly? I don't know.
The Wikipedia article on The Adventures of Pinocchio is very worth reading, by the way. Like many children's classics, it wasn't originally written for children and started out as very dark Frankenstein-like allegory about the tension between conventional behaviour and free instinct. Pinocchio accidentally kills the Talking Cricket ("Il Grillo Parlante"), which continues to advise him as a ghost; and in the serialised first version, the story ended at chapter 15 with Pinocchio being hanged. At the request of his editor, Collodi added another twenty chapters to lighten it up, in which Pinocchio meets the The Fairy with Turquoise Hair, with whose help he cleans up his act and as reward gets turned into a real boy. The Adventures of Pinocchio spawned any number of adapted and derivative works, notably a Russian analogue, Buratino.