Coal is a fairly-rare type of Terrain Special - specifically one of the Minerals. It appears as group of black streaks on the overland map, and is found on Grassland, Hill and Mountain tiles by default. It is somewhat more common on Myrror than on Arcanus.
If the Coal tile is within the catchment area of a Town, the Construction Cost of most Normal Units in that town will be 10% less than their default cost. Several Coal tiles, as well as Iron Ore tiles, can together reduce this to a minimum of 50% of each unit's default cost.
The bonuses from Coal are doubled if the town has a Miners' Guild. Coal can be changed into Gems using the Transmute spell, and Gems can be changed into Coal using the same method. Coal can be removed from a tile by raising a Volcano in that tile. Corruption temporarily removes the bonus that Coal gives to nearby towns.
Description[]
Although wood is the most common fuel for creating fire, Coal is significantly more efficient and more useful for metalworking furnaces. It is essentially fossilized organic matter which has condensed into lumps due to millions of years of pressure underneath the earth.
Coal of course is much harder to acquire than simple wood; it must be mined! Therefore, locating a rich vein of Coal allows a metal-working industry to thrive, producing a much larger quantity of weapons and armor. As a result, the cost to produce units in a town that has access to ample Coal is lower than normal.
In the game, Coal appears as a group of black streaks across the tile's surface. It is often hard to spot due to its color, and even moreso on the dank surface of Myrror.
Initial Placement and Terrain[]
Coal tiles are often rarer than most Minerals. When the world is created for a new campaign, it is quite possible that either or both Planes will be completely devoid of Coal. Myrror seems to have a better chance of having at least a few Coal tiles lying around, but there is no such guarantee. Myrror will usually also contain more Coal than Arcanus (again, if it appears in either Plane at all!).
Coal is most commonly found on Hill and Mountain tiles. It may occasionally appear on Grassland tiles, but this is rarer. Coal will never appear on other types of tiles by default, but can end up on Forest tiles due to use of the Change Terrain spell.
The only way to remove a Coal mineral is to raise a new Volcano underneath it. This permanently removes Coal from the tile - and it cannot be restored. Volcanoes can be created using either the Raise Volcano or Armageddon spells.
Mineral Effects[]
Coal is a Mineral, and thus provides a bonus to nearby towns.
When a Coal tile is within the catchment area of a Town, the Construction Cost of most new Normal Units produced in that town is reduced by 10% of its original cost. This allows faster production of new units here.
Unit Cost Reduction[]
The presence of a Coal tile within the catchment area of a town reduces the Construction Costs of most Normal Units in that town by 10%.
For example, a unit that normally costs 
200 to build now costs only 180.
With several Coal and/or Iron Ore tiles in a town's catchment area, the bonuses from these Minerals will stack together, reducing unit construction costs even further. For example, the presence of two Coal tiles gives -20% on each unit's Construction Cost. The maximum possibly bonus is -50% - i.e. each unit costs half as much as it normally would.
Note that some units require neither weapons nor armor, so production of these units is not made cheaper by Coal or Iron Ore. These are the Shamans, Priests, Magicians, Warlocks, Triremes, Galleys and Warships. Their costs are not affected in any way.
When selecting a Normal Unit for construction, you can see its actual cost compared to its default cost. This is displayed at the top of the information panel, with two numbers. The number in parentheses is the original cost of the unit. The other number is the unit's actual cost.
[]
It is possible to build two towns close enough together that their catchment areas overlap. Shared tiles are marked by a red "1/2" label, seen in each town's details screen.
When a Coal mineral occupies a shared tile, it will give half of its benefit to each town. Therefore, production of Normal Units each town will cost only -5% less than normal, instead of -10%.
Note that it is quite possible for this state to change during play, as new towns are established and existing towns are destroyed. The Coal tile's bonuses will be redistributed automatically in such events.
Miners' Guild Bonus[]
When a Miners' Guild is erected in a town that has access to Coal, each Coal tile's effect is doubled.
Therefore, a single Coal tile will reduce the Construction Cost of Normal Units by 20% rather than just 10%. Remember that the maximum reduction is always 50% (when accounting for all Coal and Iron Ore tiles in a town's vicinity).
A Coal tile that's shared between two towns (see above) will therefore generate its default bonus (-10% cost reduction) for whichever town has a Miners' Guild. If both towns have a Miners' Guild, they both enjoy the tile's default bonus (-10% each).
Transmutation[]
Using the Transmute spell from the 
Nature realm, it is possible to turn a Coal mineral into Gems.
This is done in order to increase 
Gold output at the expense of unit-production speed. It can be useful for a number of reasons - particularly when the empire is running low on Gold to support all of its existing units.
Remember that transmutation is not permanent: you can always cast the spell a second time to change Gems back into Coal.
Empires which rely on plenty of Fantastic Units instead of Normal Units may be inclined to Transmute all of their Coal into Gems.
Corruption[]
The Corruption spell can be cast on a tile containing Coal. In such an event, both the Coal itself as well as the tile it's on will cease providing any bonuses to nearby towns.
To combat this, send Shamans or Priests to Purify the affected tile immediately. If several tiles are Corrupted, Coal tiles are usually the lowest priority for Purification. Several spells, including Gaia's Blessing and Consecration, may also help if they are available.