I am a new player to Relic, tho I have played Talisman since the 80's...

I have played 4 games, and 2 of those with the new expansion.

A question came up, how does a Nemesis get healing? Only through their cards if they draw such an opportunity?

Luck with a few, very few cards or levelling up.

A Nemesis has to worry about his life status constantly as he usually doesn't has many options for healing. As his goal is to reach 25 Infamy before the Imperials fulfill the scenario victory condition, he's in some kind of race and being vanquished (and therefore halfing his Infamy score) is the worst thing that can happen to a Nemesis (while this is only a minor setback for an Imperial character)

So one valid tactic is trying to draw as many Imperium cards as possible in the early game, collecting trophies and making levels ASAP; if a Nemesis is vanquished in the early game, he does not lose much Infamy, but is reseted to his life starting quota. You pay for healing with your Infamy, so to say