From: Winnipeg, MB
First, understand what you are dealing with. The pretty map you have downloaded is the picture art that is there to make the game appealing to players, it is not the map that the computer sees/uses.
For an example of the difference look at a section of the game map that has roads and railroads, then press the "R" key. The display will show the roads and railroads the way the computer sees them - straight lines from hex centre to hex edge. Similarly use the F6 key to show the hex side colours that tell you what the transition between hexes is - red means you cannot travel across, dark blue is water that requires amphibious ships to cross, purple is fordable water, green is good for all types of movement.
The computer code is in three files: pwhexe.dat, pwzlink.dat, and pwzone.dat. These are in a folder called AE Stock Map Data.
The visible sections of the map are in a bunch of separate .bmp files that fit together to form the map. These all start with WPEH or WPEN e.g. WPEH08.bmp is the map section that includes all of Indochina.
All the map art pieces belong in the Stock Map Art subfolder within the AE Stock Map Data.
To complicate the issue there are four versions of the map - stock map or extended map, with stacking limits or without stacking limits. I do not know if Chemkid's art that you downloaded is for the stock map without stacking limits (original game map) or one of the others. Look on the download site to see if it tells you. If it is for one of the other map versions you will have to change both the art and the data files for the map.
Once you understand which map you want to install, create a new folder called "original map" and transfer all the files you are replacing over there as a backup.
Now take the new map art and data (if you need to change that) and put them into the AE Stock Map Data folder and Art subfolder.
For the final wrinkle, some of the map versions may require you to install a modified (player designed) version of the game like Reluctant Admiral or Da Big Babes. I don't play those so I cannot advise on that. Can someone else clarify that please?
No matter how bad a situation is, you can always make it worse. - Chris Hadfield : An Astronaut's Guide To Life On Earth