Cold Damage is a type of Physical Damage that is only delivered by the 
Nature spell called "Ice Bolt".
Cold Damage is similar to basic Physical Damage types (such as Melee Damage) in the way it harms the target: The attacker must make 
To Hit rolls to determine how many times it has hit the target, and then the target must make 
Defense rolls to determine how many hits it managed to block. All unblocked hits are then translated into simple 
Damage which is applied to the target, potentially killing one or more of its 
Figures.
Cold Damage is considered a sub-type of Magical Damage. This means that it is almost entirely ineffective against targets possessing Magic Immunity. On top of this, Cold Damage is almost always useless against targets possessing Cold Immunity.
Effect[]
Cold Damage behaves the same way as Melee Damage or Ranged Damage, except it may trigger two different kinds of immunities possessed by the target (if any), making it ineffective against such a target.
To Hit and Defense Rolls[]
Like other types of Physical Damage, Cold Damage attempts to inflict actual Damage Points on the target. To do so, the attacker must make To Hit rolls to determine how successful the attack was, and the target may make Defense rolls to determine how much damage it managed to block.
The attacker makes a number of To Hit rolls equal to the strength of the Cold Damage attack. Only the Ice Bolt spell delivers Cold Damage, but its strength is adjustable by investing more 
Mana into it at casting time. For example, an Ice Bolt spell with no extra Mana invested attacks with a strength of 
5, so it makes 5 To Hit rolls.
Each of these rolls results in a number between 1 and 100. For each roll that comes up equal to or lower than 30, the game registers one hit against the target.
The target then makes a number of Defense rolls equal to its current 
Defense score. Each roll results in a number between 1 and 100. For each roll that comes up equal to or lower than the target's current To Block score (which is usually 30 for most units), the game reduces the number of hits against the target by 1.
At the end of this process, the game tallies up the number of unblocked hits (equal to the number of registered hits minus the number of blocked hits). It then applies Damage to the target accordingly - 1 per unblocked hit.
As with all other types of Physical Damage, if the target has lost one of its Figures due to this damage it may make another set of Defense rolls to try and block more damage. The process only ends once all hits have been translated into Damage or have been blocked by these Defense rolls.
For a more thorough explanation of the process, see Physical Damage.
Immunities[]
Cold Damage is always delivered by the Ice Bolt spell. Since it results from a spell, it will be completely blocked by any target possessing the Magic Immunity ability. Such a target will suffer no damage from the spell, regardless of how much extra Mana was invested into it.
Cold Damage is different from other Magical Damage types in that it can also trigger another immunity called Cold Immunity. In other words, if the target possesses Cold Immunity, its Defense score is raised to 50 whenever struck by a Cold Damage attack.
Thus, when the target possesses this ability, the attack needs to be exceptionally powerful - otherwise it would have no chance of busting through 50. The Ice Bolt spell can be this powerful, but you would need to invest a large amount of Mana into it, and even then the chances of getting through Cold Immunity are slim.
Cold Damage vs. Blizzard Damage[]
The Ice Storm spell does not actually deliver Cold Damage. Instead it delivers another unique damage type called Blizzard Damage, which (depending on circumstance) can behave exactly like Cold Damage or completely different from it.
When Blizzard Damage is used against a 
Single-Figure unit, it behaves exactly like Cold Damage. The process is explained above in this article, and works the same for both damage types.
However when used against 
Multi-Figure units, Blizzard Damage is significantly more potent than Cold Damage due to the way it is processed. Instead of making a single set of To Hit rolls against the target, and allowing the target to make a single set of Defense rolls, Blizzard Damage will actually strike each Figure in the target unit independently of the others. Each target figure also makes its own attempts to block the hits inflicted directed at itself. Only after all rolls have been completed is Damage applied to the target unit as a whole.
The end result is that against Multi-Figure units, Blizzard Damage can inflict far more Damage than would a Cold Damage attack of similar strength. This is why Ice Storm is so powerful (on top of the fact that it can be delivered against several targets simultaneously...).
Nonetheless, in all cases the immunities that apply against Cold Damage work the same way against Blizzard Damage.
For a thorough explanation, read the Blizzard Damage article.
Sources of Cold Damage[]
The game contains exactly one source of Cold Damage: The Ice Bolt spell. This is a Common Combat Instant from the Nature realm, whose only purpose is to inflict a certain amount of Cold Damage on the selected target.
The amount of damage inflicted is variable - controlled by the amount of extra Mana invested into the spell when it is being cast. The "basic" Ice Bolt spell, cast with no extra Mana, delivers only 5 Cold Damage points. The fully-powered spell, cast with an extra 40, delivers 45 Cold Damage points. The ratio is 1 for each extra 1 Cold Damage.