I ran some stats for you (from our data on Hostelz.com, a travel website that I represent) and currently 97% of hostels provide free bedsheets, and the remaining 3% charge a fee. Towels are a different matter. Currently 50.5% of hostels include free towels, 46.9% charge a fee, and 2.6% don't offer towels at all.
Over the long term, the trend is actually moving in the opposite direction of what you may think it is. In the past hostels traditionally didn't provide bedsheets or towels at all. When staying in hostels, you were expected to bring your own "sleepsheet" (usually made from two bedsheets sewn together). As recently as the early 2000s, guidebooks recommended always having your sleepsheet when staying in hostels because most hostels charged extra if you didn't bring your own sheets, and some didn't offer sheets at all.
Over the past couple decades, hostels have been more and more offering amenities similar to what you would expect from hotels (and they've been raising their rates as well). Some may still charge for sheets because they traditionally have always done that, but some hostels may be just doing it as a way to profit from added fees (the Ryanair business model).
How to Find Out
To answer your question about how to find out ahead of time which hostels charge for sheets or towels, most of the hostels' own websites don't include that info from what I've seen. If you're looking on Hostelz.com, we list that information in the column on the left side of each listing, usually including the specific price they charge if the hostel provided that information. Other websites may list information as well (Hostelworld for example will usually say "sheets included" if they're free, so if you don't see that, there may be a fee).
Consider Bringing Your Own
Personally I still always bring a sleepsheet (or "travelsheet") with me anyway. I just like sleeping in my own familiar sheets. You could bring a simple bedsheet with you, or if you don't mind spending some money, you can get a really nice silk travelsheet. Silk is ideal because it's super lightweight, compacts to a very small size, durable, breathable, and super comfortable.