I use what I have, and that can be coconut coir, stove pellets broken down into sawdust, leaves, chopped/dried weeds, used bedding from pocket pets, and/or paper. Any combination of these make pretty good bedding. It's also important to note that after a while whatever you put in there as food also becomes part of the 'bedding'.
But yes, straw or hay works as well. If you're starting from scratch to build a bin using straw or hay, I'd say chop it up in smaller pieces at first to give your worms a few inches to hide in. Then you can pile on more roughly chopped hay, and they'll eat it from the bottom.
Straw and hay should be fine. I would prefer straw over hay since it is more absorbent. Just try not to get the system too wet. In my experience with redworms, it seems like the bedding serves mainly as a carbon sponge and to regulate moisture. Since most people are using kitchen scraps which are somewhat nitrogen rich and wet, it helps balance the system.
If you generate a fair amount of compost, you can rotate it into the worm bin.
The compost that you remove periodically will be supercharged with worm tea.
The bedding they use throughout the winter will be ready for spring.
Should help make a wonderful potting soil.