Of course, the first knee-jerk countermeasure for this is "block ICMP". While the majority of that protocol should already be blocked (for other reasons), the obvious countermeasure may not always be the best. In other words, blocking ports/protocols because they can be abused will lead to the firewall blocking everything. A better approach is to configure your firewall for "normal" operation and then monitor what you allow to pass for anomalies.
What the article demonstrates is the embedding of one protocol within another. It's the reason why various programs are difficult to block at Layer 3 (IP addresses) or Layer 4 (Ports/Protocols).
Some programs (e.g., instant messengers, P2P) are adaptive and can use a number of addresses, ports or transport protocols.
While all firewalls (okay, most) filter IP protocols 6 (TCP) and 17 (UDP), they are often configured to pass others. Many will pass at least some subset of protocol 1 (ICMP) and one or more other routing protocols. Most are not useful for covert channels as, if a network is implemented correctly, the protocols are blocked further upstream. Others are. ICMP is often used for tunneling because certain types of ICMP packets will pass through the firewall and the packets can carry a decent sized payload.
This is why, contrary to what the firewall and IDS vendors tell you, the job of network security is largely a reactive job. The majority of your problems will be internal and you need to face the fact that a few of your users know more than you, don't believe they'll get caught, and have more "access" than you realize.
What you have going for you is human nature (the second option in that last sentence). People who don't believe they'll get caught won't remain "in the background". They'll usually try gradually more daring (and noisier) things.
The most effective countermeasure is monitoring your metrics (especially the most boring ones!) for anomalies, reading your log files, and spot-checking content for normal shape, size, and lifespan. The majority of corporate users (if not all of them) are granted the minimal access needed to perform their job. The content they generate should be boring as hell (HTTP on port 80, SMTP on 25, very small ICMP packets, etc.) Your job includes having to watch for the non-standard stuff (odd flags turned on, non-standard packet sizes, "noise" on port 25 or 80, etc.).
Oh! And make it a point to track down the small stuff too (though you may not always have the time). They'll often lead to the larger "stuff" and may also indicate other problems (misconfiguration) within the network.