From my experiences at hotels, I'm used to toiletries (soap, shampoo, etc.) being provided.
Do hostels also provide these, or do I need to bring my own? Do hostels provide towels as well, or will I need to travel H2G2-style?
As already mentioned toiletries are very rare. Towels depend a lot but if the hostel doesn't provide them for free they usually provide them for a fee (all the cases I've witnessed were for an affordable fee).
I was never in an hostel without toilet paper. In the worst case if you ask at the reception they will quickly solve that.
A rare case, but that you should be prepared for (check in advance) is the possibility of the hostel not providing bed linen by default. Either you have to bring it or rent it in the hostel. Sometimes sleeping bags are not accepted as a bed linen replacement.
A good source of information before traveling is www.hostelworld.com
You can find an intersting article here about what to expect from an hostel.
Here's another a bit more generic.
Almost always, you bring your own, however...
Hostel sites like Hostelbookers often indicate whether or not items like towels are available for rent, or provided.
Some I've seen will sell toothpaste and deodorant and the like.
Personally, I bring a towel and toiletries, and almost always I've needed them. It's generally a surprise when I don't.