You should definitely hint at his resurrection after he "dies" and before you see him the second time.
Even better, you should leave hints even from the beginning of the game, especially if it is an important plot twist. That way it is integrated into the story rather than just tacked on.
For example, in the Sixth Sense, there are clues right from the beginning of the film, and all the way throughout. When the boy first meets Bruce Willis, he is scared (we assume its because he is scared about the psychologist learning his secret) and whenever Bruce Willis is around it is cold (we assume there is another ghost in the room).
Which brings me to another point... your clues should always be hidden. In mystery writing they say, "if a person is shot in the third act, put a gun in the gun rack in the first act." The fact that the gun is mentioned in passing as the room is being described means the reader's attention won't be drawn to it. Not until the person is murdered by the gun, and the reader will say, "Of course, why didn't I think of that!"
Basically, all the clues as to how and why he will be resurrected should be presented early on, but should be hidden by presenting them in a way that the player will assume they mean something insignificant/different.
So for your character, if he heals himself with herbs, have him a keen gardener with a green house (lame but you get the idea.) Or if he was born with a magical ability, have every one talk about his twin brother who died, and that is why he was evil (when actually, he had been killed and when he came back to life he hid his ability by assuming the identity of a non-existent twin).