The best way to do this is to mandate a minimum time off. I've been lucky enough to work a couple places where this was the policy. This has to be a top-down initiative.
>Increase headcount
Definitely. I've seen short-sightedness prevent this from happening and it doesn't end well. In fact, I once quit a job where I was gradually taking on additional work (without additional pay, of course). I probably wouldn't have quit if I had one additional person to help me. When I expressed my concern I got "we can manage our workload right now." An ounce of prevention is worth a pound of cure.
>Express gratitude
Yes, but do it with cash. Don't send trinkets to people's houses - just give them the cash instead. It can get really insulting when you're rewarding people with silly trinkets then saying there's no room in the budget for a pay increase. (Been there).