Herald-Mages are Heralds with the Mage Gift -- a rare gift of True Magic in addition to their Mind-Magic Gifts. A Herald-Mage might have a strong Mage-Gift and a weak Mind Gift, or alternately a strong Mind Gift and a weak Mage-Gift.
Herald-Mages hold many duties and many positions within the Circle, to include magical defense of Valdemar and training of MageGifted Heraldic pupils. In the time of Vanyel Ashkevron, four (in the seats of North, South, East, and West) chosen Herald-Mages also maintained the Web that alerted them to danger that threatened Valdemar. This duty was removed (in part due to the dwindling number of MageGifted Heralds) when Herald-Mages Vanyel, Savil, Lissandra, and Kilchas (with the aid of their companions, overseen by Herald Tantris) set the Watch spell (linking all Heralds to Valdemar) and created the Heartstone, also calling the vrondi to 'watch' mages within Valdemar's borders in the effort to make those with ill-intent paranoid and disquieted enough to leave.
Due to the actions and machinations of Leareth, Valdemar's mages have been systematically culled, and any who have the MageGift only have it as potential. To cope for this loss, Vanyel Ashkevron (Magic's Price) chose to suppress the knowledge of True Magic from Valdemar with the help of the Companions, to keep the people from doubting the abilities and capabilities of Heralds. After the death of Vanyel, there were no new Herald-Mages until Selenay's reign when his descendant Princess Elspeth (abdicated) became the first Herald-Mage in over half a millenium.
While it is true that the MageGift was essentially dormant since the time of Vanyel, it is speculated that many Heralds have had MageGift and it was trained as something else. For example, Herald Mags could also use the Heartstone in the palace at Haven. Further, when he invoked truth spell he and his mentor Jakyr both saw the vrondi instead of a blue mist. However, since Mags had his gift training mostly taught by his Companion, Dallen and the Companions helped to suppress the knowledge of magic, it is not known if Mags was truly MageGifted, or simply had the Mage Gift in potential, albeit stronger than other known instances.