Our DD6 went through the phase of experimenting with lying, and we haven't caught her in a lie in ages, so I guess what we did worked in her case (or she's just gotten better/more selective about it). Here are some ways we attacked the problem:
- Told the story of "The Boy Who Cried Wolf" whenever she was caught in a lie. I'm not sure how the classic version ends, but in ours, the boy was eaten. The message was that she needs people to believe her, and she won't be believed if she keeps telling lies. I'd also explain how trust is hard to gain and easy to lose.
- Double-checked everything she said while she was having that phase. This sent two messages... the first being that it's not worth it to try to lie, because she's going to get caught. And the second is for her to experience what it's like to be distrusted. So for example, if she'd been across the street at her friend's house, and she came home asking for junk food, I'd ask her what she'd eaten across the street... and then I'd call the parents.
- Mitigated/eliminated punishments when she told the truth. This emphasized the positive value of being honest. So if something was spilled or broken, hey, accidents happen, we'll help you clean it up. Just don't lie about it or cover it up, because that gets a punishment.