Fatigue is a meter that will appears whenever you swim or fly to far from land. The fatigue meter act much like the breath meter, it will appear on screen and start to deplete itself unless you return to swallower water. Once it is full depleted, it will start dealing damage to you. This damage can be healed.
Fatigue zones are determined by the 'height' of the floor under water. If you are swimming, you will usually see a sharp decline in the ocean's bottom right where the fatigue zone starts and the water is usually darker as well (which is the only indicator flyer will get before the bar pops up). It is not linked to time spent swimming and fatigue thus never occurs while swimming in and in-land lake or rivers.
There is no real way to combat fatigue, there's no 'anti-fatigue' potions or abilities. The faster you fly/swim, the farther in you'll go into the fatigue zone, but there's really little point in doing so.
In short, this is World of Warcraft's way to prevent you from going off the map and into the distance, rather than using invisible walls.