What regulatory bodies are there?
Global

Starting from the top, we find the International Civil Aviation Organisation (ICAO), which is a United Nations agency. ICAO was formed in 1944 when the Chicago Convention was signed, and initially had 52 member states. Today, 191 states worldwide are members of ICAO. The headquarter is in Montreal, Canada, and there are 7 regional offices.
ICAO standards and other provisions are developed in the following forms:

Standards and Recommended Practises (SARPs):

Technical specifications adopted by the Council of ICAO in order to achieve the highest practicable degree of uniformity in regulations, standards, procedures and organization within air navigation. Member states will conform to standards and will endeavour to conform to recommended practises. States are invited to inform ICAO of non-compliance.

Procedures for Air Navigation Services (PANS)

PANS comprise operating practises and material too detailed for SARPs. They are suitable for application on a worldwide basis. Member states are invited to publish differences between national procedures when considered important in the interest of safety.

Regional Supplementary Procedures (SUPPs)

SUPPs are supplementary procedures which are only valid within one of the ICAO regional office regions. For example, there are supplementary procedures published only valid within the European/North Atlantic region.

Also worth mentioning are the International Telecommunication Union (ITU) and the World Meteorological Organization (WMO), both of which function on an (almost) global level.

Regional

Below ICAO we have regional organisations. As an example, in Europe, the European Union (EU) provides legislations for its member states. Non-regulatory organisations, such as the European Aviation Safety Agency (EASA), assist the EU in developing regulations (but the EU, not EASA, is the regulatory authority).

Some areas do not have regional regulators like the EU. In such areas, national regulations are handled directly by national regulators. Within the EU, countries also have national regulators – but they are bound to base their regulations on EU regulations.

National

Below the regional level we have national regulators, commonly referred to as civil aviation administrations (CAA). Each country will have their own CAA. One that you will often hear about is the Federal Aviation Administration (FAA), which is the national regulator in the USA.
Generally speaking, a national regulator will be following framework regulations published by the national ministry of transport. The term ministry of transport is also sometimes applied to the departments or other government agencies administering transport in nations who do not employ ministers. The framework regulations from the ministry of transport are largely based on ICAO SARPs, PANS, SUPPs and any regional regulations (such as EU regulations).

The national regulator will publish detailed regulations, which are adapted by the air navigation service providers, as well as airlines, pilots, air traffic controllers, maintainence companies etc. etc.

The service providers, commonly referred to as ANSPs, are the organisations actually providing air navigation services, such as communication, navigation and surveillance equipment, meteorological services, air traffic management (including ATC), aeronautical information and search and rescue. Most ANSPs operate within a single nation, but there are also multinational ANSPs, a few examples are ASCENA (Africa and Madagascar), COCESNA (Central America), EUROCONTROL (Benelux) and NUAC (Sweden and Denmark).

The service providers work together with the national regulators to develop detailed procedures, but do not (usually) have any regulatory authority.