Warning, parts of this may be a bit spoily, if you can decipher it.
I think holybanana intended on setting out a coding tutorial on this topic, but I decided to have a crack at it and have figured out how this is done. I reverse engineered it from differences between IVAN and LIVAN.

I will show how to add a new location to the worldmap. In this example I will add the rocket launch pad named Baikonur, situated amongst leafy forest. The parts I added are in bold.

1) In define.dat and in ivandef.h add the line: # define COSMODROME 5
i.e. I inserted into the following lines:

...
#define RANDOM 0
#define ELPURI_CAVE 1
#define ATTNAM 2
#define NEW_ATTNAM 3
#define UNDER_WATER_TUNNEL 4
[b]#define COSMODROME 5[/b]
#define UNDER_WATER_TUNNEL_EXIT 0x80
...

2) In wterras.h add an owterrain (over-world terrain) called cosmodrome (as per the other entries). For this example:

...
[b]OWTERRAIN(cosmodrome, owterrain)
{
 public:
  virtual const char* GetNameStem() const;
  virtual v2 GetBitmapPos(int) const;
  virtual int GetAttachedDungeon() const;
};[/b]
...

3) In wterras.cpp add a const char* cosmodrome (to the best of my knowledge, this adds the new location to IVAN, links the location bitmap to its position in wterra.pcx and attaches the relevant dungeon). Add the following lines of code:

...
[b]const char* cosmodrome::GetNameStem() const { return "The ancient rocket launch-pad, Baikonur, looms up from the forests"; }
v2 cosmodrome::GetBitmapPos(int) const { return v2(16, 64); } [i]// I have used the same bitmap for new attnam in wterra.pcx, for simplicity[/i]
int cosmodrome::GetAttachedDungeon() const { return COSMODROME; }[/b]
...

4) To worldmap.cpp add the CosmodromePos codes, the SetEntryPos(COSMODROME, CosmodromePos) and the GetWSquare. This is slightly more elaborate, I want the cosmodrome to be situated in a leafy forest, so I had to fix that in as well.
Firstly inside the function: void worldmap::Generate(), I added another condition in this for loop, and in the statements that follow I added a couple of other lines:

...
for(uint c = 1; c < Continent.size(); ++c)
      if(Continent[c]->GetSize() > 25 && Continent[c]->GetSize() < 1000
	 && Continent[c]->GetGTerrainAmount(EGForestType)
	 && Continent[c]->GetGTerrainAmount(SnowType)
	 [b]&& Continent[c]->GetGTerrainAmount(LForestType)[/b])
	PerfectForAttnam.push_back(Continent[c]);

if(!PerfectForAttnam.size())
      continue;

    v2 AttnamPos, ElpuriCavePos, NewAttnamPos, TunnelEntry, TunnelExit[b], CosmodromePos[/b];
    truth Correct = false;
    continent* PetrusLikes;

    for(int c1 = 0; c1 < 25; ++c1)
    {
      game::BusyAnimation();
      PetrusLikes = PerfectForAttnam[RAND() % PerfectForAttnam.size()];
      AttnamPos = PetrusLikes->GetRandomMember(EGForestType);
      ElpuriCavePos = PetrusLikes->GetRandomMember(SnowType);
      [b]CosmodromePos = PetrusLikes->GetRandomMember(LForestType);[/b]
...

Further along, still in worldmap.cpp, there is an if-statement after which is added:

...
if(!Correct)
      continue;

    GetWSquare(AttnamPos)->ChangeOWTerrain(attnam::Spawn());
    SetEntryPos(ATTNAM, AttnamPos);
    RevealEnvironment(AttnamPos, 1);
    GetWSquare(NewAttnamPos)->ChangeOWTerrain(newattnam::Spawn());
    SetEntryPos(NEW_ATTNAM, NewAttnamPos);
    SetEntryPos(ELPURI_CAVE, ElpuriCavePos);
    GetWSquare(TunnelEntry)->ChangeOWTerrain(underwatertunnel::Spawn());
    SetEntryPos(UNDER_WATER_TUNNEL, TunnelEntry);
    GetWSquare(TunnelExit)->ChangeOWTerrain(underwatertunnelexit::Spawn());
    SetEntryPos(UNDER_WATER_TUNNEL_EXIT, TunnelExit);
    [b]GetWSquare(CosmodromePos)->ChangeOWTerrain(cosmodrome::Spawn());
    SetEntryPos(COSMODROME, CosmodromePos);[/b]
    [i]PLAYER->PutTo(NewAttnamPos);[/i]
    CalculateLuminances();
    CalculateNeighbourBitmapPoses();
    break;
...

SPOILER ALERT. Click here to see text.

5) Then hit the Compile button. IVAN will crash if you enter into the location and haven't added the dungeon in dungeon.dat

6) Finally add the dungeon to dungeon.dat, from this position it is only a matter of scripting the dungeon to your hearts content. DON'T forget to increment the number of dungeons and levels! Enjoy.