Who decided which airspaces not to fly through and how?
One major driving factor is whether a permit is required. Many countries in the world require a permit even for overflight.


(source)

Depending on country to country, airline to country and general relations it may be more advantageous for a carrier to get permits in one country than it would be in a close neighbor. Going a bit out of the way (burning extra fuel ultimately) may be less costly than delays related to permit issues, etc.

In some cases there are also prohibited airspaces within a country. This is simply airspace you cant fly over for regulatory reasons (generally security). While some of these airspaces are small, some areas can be quite large in size.

While increasingly a smaller case not all aircraft are equipped to fly through all airspaces. Different regulating bodies may require different gear on board for a given flight. Aircraft may be prevented from entering a given airspace if not properly equipped or certified. 

On any given day routes may be amended for weather or potential weather hazards.

As @mins notes in the comments, this answer covers areas avoided for safety reasons.