If the Herald that died is the King's Own or Queen's Own, then the Companion will choose another Herald. This is because the position of King's/Queen's Own is so important that it needs to be filled. Also, the position of King's/Queen's Own Companion is so important, that they do not have the option of wallowing in depression or withering away and dying. They have a duty to bond again to another Herald who will then become the King's/Queens Own Herald.
It is mentioned in a number of books that the profession of being a Herald is dangerous, so Heralds do not tend to die of natural causes.
"Heralds didn’t tend to grow old. Even in times of peace, they lived lives that lowered the odds of them dying in bed to slightly less than negligible." Moving Targets and Other Tales of Valdemar
I would imagine that if/when a Herald does die of natural causes, their Companion would soon follow them into death... The same as they do when Heralds die unnatural deaths.
"She'd die, lad; Companions very seldom outlive their Chosen. And she Chose you. If you die, she dies; she'd probably pine herself to death, and she does not deserve that." Magic's Pawn