How old does a child have to be to be lying on purpose? How old are they before they can understand the concept of a lie vs the truth? What about not the truth vs the truth?
This documentary film (german) says that children above the age of 4 years are able to lie on purpose. The ability to put oneself in the position of someone else in order to foresee how the lie effects the other person is a requirement for lying, they say.
I found a good article on telegraph.co.uk that answers this question. But first, what counts as "lying"? The studies mentioned in the article are pretty broad, and include any sort of intentional deception. Taking that definition, babies can lie as early as 6 to 8 months!
It goes on to say that later, when kids are around 2-year-olds, their lies can become more sophisticated. They'll say "I don't care" when threatened with punishment, even if they do care.
When I was in college, back in the 80s, I wrote a paper for some psych class on truth and lies. In it, I came to the conclusion that there's several different types of truth and lie. for convenience, I classified them in shades of grey.
When faced with the question "did you take my money?" and the person actually did take the money...
and several variations in between that I won't go into. The point i'm trying to make is that there's a lot more to truths and falsities than people care to admit (lest they reveal the intentions at the core of their personality). It takes quite a while before a kid can understand the subtleties of interpersonal relationships, let alone actively attempt to manipulate them.
Fake laugh and cry are not about deception (a pretty advanced concept) and all about self-advantage. In other words, they're not trying to get you to give up something you value, they're just trying to get something for themselves. Any child up to about 4 is going to act that way. Deception involves clear comprehension of the other person's point of view. It's actively attempting to thwart the other persons defenses, in many cases so that they give up something that has value. I'm no psychologist, but i'll bet that's not something you'll see till minimum 8 or 9.
So lets say a 3 yo playdate. Finn starts crying and throws a brick (megablock) at the other kid.
If Finn and Marceline were 13, we would assume that she was lying to stay out of trouble. a 3 yo Marceline just wanted more goldfish, probably took the last 3 out of Finns cup without realizing (dare i say without caring) that they belonged to someone else. A common interaction that has ZERO to do with lying. It's all about property. And hunger.
Punishment? Nah. establish the boundaries "this is your cup, marceline. THAT one is finns" and give em a few more goldfish and this crisis is averted. Of course, if it continues, marceline needs to be dealt with, but that's a different topic.
toddlers generally don't understand the interpersonal dynamics that are the foundation to lying. even bad bad toddlers that hide stuff aren't being deceptive, it's all about something they want... even if a 4yo is constantly hiding daddy's cigarettes. they really just want more attention from daddy.
Bottom line: what do you do? when you hear hooves, think horses not zebras. The solution to the problem is a simple one based on the childs personality, not the adults sensibilities.
A few additional thoughts to @monsto's answer:
Roughly till the age of 7 (+-3), children live in a magical world, which is very different from how we adults experience (or seem to experience) things. Their world is shaped by their own thoughts, desires, images much more than by some solid "objective", "external" reality. Very often, they are confabulating this world and its events, rather than describing as we would expect. Just recently, during the holiday season, my younger daughter told us that she saw an elf peering through the window, and they both hailed each other. Was she making up a story? Yes. Was she lying? Absolutely not.
OK, you might say, this is a cute little story. Let's see another one. Jim notices that someone took money from his coat pocket, and they find out it was his elder son Joe (8). They actually find the missing money in Joe's bag. When asked "did you take Dad's money?", Joe says no. Is he lying? By adult categories, yes. However, by child categories, it is a very different story. Joe recently got a little sister, Sarah. Naturally, a lot of attention and energy in the family is now shifted from him to Sarah, which is very frustrating to him. Stealing is a (misguided) attempt to get more attention and care from his dad. When confronted with the question, he wishes he had never done it, and expresses this wish by saying "no".
Bottom line is, it is often too easy and tempting to apply adult terms and categories to what children do and say, and act out of these classifications. However, children aren't little adults. Without actually understanding (or rather, feeling into) their situation and motives, it is dangerous to judge (much less to punish) them. Moreover, since the pace of personal development is extremely varied between individual children, 3 children of the same biological age can be on very different cognitive / emotional / social levels.