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?
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.
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.
Hotels are targeting businessmen travelling with a briefcase. You usually don't carry soap or towel in your suitcase.
Hostels are targeting backpackers which are expected to bring a lot of things with them. While all the hostels I've stayed in had soap in the bathroom, and they've also provided towels (some for free, some for an extra charge). Shampoo, razors, body creams, if available, were what previous guests had left behind. So simply take your own things with you.
In case the weight is the extreme consideration (air travel) check if there's a supermarket nearby. It's hard to expect such things would be hard to purchase in the place there are hostels, maybe with the exception of German-speaking countries on Sunday ;)
The towel - you can take a little one with you. In the worst case it would be a bit harder to dry your whole body, but it's recommended to have a little towel with you always when you travel - if you'd need to clean yourself in a plane or train etc.