Diatomaceous earth. You need to get FOOD-GRADE stuff (or the Red Lake Earth your feedstore may sell, which is DE mixed with clay), the pool-filter or insecticide-grade DE is considerably more harmful to lungs. It is totally optional whether to use DE.
I use wood shavings and straw. Can hens have hay too?
Yes, but it is more expensive, will mat together worse (harder to clean), and a fair number of people have problems with hens getting impacted crops from eating it. I wouldn't use it myself, but some do with no problem.
You might consider using ONLY shavings OR straw, since unless the straw is chopped it is usually a whole lot harder to clean (or turn) a mixture than just shavings or just straw. Even with any of a variety of deep litter methods, you still can't be letting things get all matted and awful, which is harder to prevent with whole straw.
I'm thinking of the deep litter method. Sounds like it should work, especially for cold winter months that we have here in Eastern Canada.
If you are going to try using deep litter in Eastern Canada you need to have VERY AMPLE ventilation, like really very much more than you may think of, instead of trying to keep the coop 'tight' to 'hold in heat'. A very traditional and widespread Canadian custom is giving yer chickens frostbite and respiratory problems by shutting the coop up for the winter, and you are under-ventilated to start with, trying to leave the poo in there for deep litter will only make the problem worse.
(That said, I *do* use a version of deep litter management, and I live not quite an hour north of Toronto... all's I;m saying is that it is not one size fits all, and in many cases the way people do things up here it can make things worse)
Good luck, have fun,
Pat