I used myself as a horrible example. (Past tense, because DS can now tell my story himself, so I don't have to!) I (thanks to not-so-great education) went through the whole of school thinking maths was something I should always be able to do first time, no trouble, 100%. When I finally hit problems that were hard, I had a *lot* of work to do learning to deal with that situation, practically and emotionally. (In maths, if you go far enough, you will hit this situation: anyone who doubts it should go and prove Goldbach's conjecture, and then come back for the next exercise.) Therefore I've always tried to make sure DS has some work to do that is so hard he can't do it, and some that he can but only if he really works. I've also been completely open with him about what I'm doing and why.
You do have to really believe it yourself! Resist any temptation to be pleased when they do an entire exercise sheet with no trouble: remember to be disappointed, because it means they didn't get a chance to learn with optimal efficiency that time. Celebrate struggle (when it eventually leads to success, but even when it doesn't). Point out progress - let them experience finding something easy now that they remember finding hard before. Etc.
