What is the history and process of designing new waypoints and airways?
In systems theory, emergence is the &quot;phenomenon whereby larger entities arise through interactions among smaller or simpler entities such that the larger entities exhibit properties the smaller/simpler entities do not exhibit.&quot;
I think this best describes how the airspace design came to be from nothing.
In the beginning...
There was air mail. The pilots had hard time finding their way despite the US Postal Service installing lighted beacons connecting the major routes.
Then came a 20-something year old chap by the name of Elrey Borge Jeppesen. He made a cheat sheet that everyone wanted. The aeronautical charts and the AIM's precursor was born. He even included farmers' telephone numbers for weather reports.
The Department of Commerce then funded a better airway system. First there was the four-course radio range, which gave way to VOR and NDB. NDB is now extinct in the wild, and VOR is vulnerable. GPS gave birth to the free route airspace.
(SkyVector) Airways black hole in Europe (Free Route implementation).
Who draws the map?
Everyone. Each country designs its airspace, but since airspaces share borders (even over water), countries also work together. Article 68 of the 1944 Convention on International Civil Aviation says:

Each contracting State may, subject to the provisions of this Convention, designate the route to be followed within its territory by any international air service and the airports which any such service may use.

Or, as the Australian Department of Infrastructure and Regional Development puts it:

Before an airline can operate international services to another country, the government must first negotiate a treaty level agreement with the destination country's government. These treaties are known as bilateral air services agreements.
The result is that international aviation is regulated by a complex web of over 3000 interlocking bilateral air services agreements.

Map of bilateral air services agreements.
International waters
(Source)
In civil aviation, the Flight Information Regions (born c. 1947) share borders. They are not limited to 12 NM offshore like territorial waters. In the Mediterranean Sea for example, Egypt and Greece share a border. So does Scotland and Norway across the North Sea. Along the shared border are waypoints shared by both countries, they form the entry/exit points to/from each county's national air system.
Airways that cross borders form regional networks, they have different prefixes from airways that never leave an FIR. See: ICAO Annex 11.
Really, who draws the map?
The air navigation service provider (ANSP) of each country, by working with the national aviation authority (NAA), other countries, airlines, ICAO, IATA, etc.
An example would be the FAA redrawing the map for the NY/NJ/PHL airspace.
Each ANSP or NAA will have an airspace design unit responsible for the analysis, design, and simulation of the airspace system, among other tasks. Guidelines and regulations exist on the local and international levels for every aspect of the route and sector design. An example would be ICAO Annex 11.
A typical team and process (via icao.int):

This process takes 280 days to complete.
The bigger the scale, the more cooperative the process becomes, for example check this airspace design webpage for the EU.
(Source) Software for airspace design.
Demand and technology
It's supply following demand. You don't see many airways above the Tibetan Plateau for example. And of course the technological advances are a huge driving force. A bend in an airway due to a mountain range shielding a VOR can now go away thanks to GPS, RNAV, RNP, etc.