Well, yeah, then. You can definitely do most of it with simple flavor text. I'd be VERY careful about adding new abilities that let someone decapitate an immortal who isn't helpless, down&dying, or otherwise toast. It can happen against PCs as well as NPCs, and having your dude killed in the first few games is just a bummer.
Maybe: If, on a critical confirmation roll, you roll a Natural 20, the victim takes damage for the critical and then has to make a Reflex save, DC=Damage Dealt, to avoid a crit. That lets random decaps happen every once in awhile in mid-combat, but it doesn't make it a game-breakingly common occurence.
Sensing the Other Dude:
1) Generally happens at a distance of 50-500 feet? (Can be close enough so that the immortal only has a few seconds to prepare, but can also be a fair ways away.)
2) Make feats like "Extended Sense", which allows you to roll twice and take the farther result, meaning that you are more likely to sense someone before they sense you; "Familiar Sense", which lets you pick a friend or enemy and learn the pattern of their essence, so that you can tell if it's your buddy approaching or an enemy; and maybe "Mask Presence", which lets you force the other side to roll twice and take the closer result, as your presense is harder to detect.
3) Decide whether you're playing by "Movie Rules", "Show Rules", or "Both":
Movie Rules: Immortals have borderline ESP, channel energy into superhuman strikes, and can generally do a lot of things that ordinary people can't. They might have superhuman immunities, too -- like being able to walk up and kill someone who's unloading a clipful of bullets into them.
Show Rules: Immortals can't die. Other than that, they're as human as you or me. They can breathe underwater, but they can't walk through a hail of bullets -- they just die (or heal) and then come back.
Both: Immortals start out using Show Rules, but can eventually attain Movie Rules status at extremely high levels (like, by getting a lot of Quickenings).
4) Decide how to handle hit points and immortal healing:
a) Immortals have Fast Healing. Not terribly flashy, and it loses the "little arc of electricity, and then the wound is gone" cuteness, but it's easy to implement.
b) Track "wear down" wounds and "big bloody" wounds differently. Because immortals can get worn down through combat, moving slower, getting tired, gradually opening themselves up for that big final strike, they shouldn't heal hit points all that quickly -- because "moving slower" and "getting tired" equates to hit point damage. A 90-hit-point character at half hit points is not bleeding -- he's winded and shaken by a good fight. That is, unless that 50 hit points of damage came in one hit, in which case he's got a long cut across his arm or something like that. Track damage from Critical Hits separately, and have that heal at an accelerated rate, while your ordinary hit points heal through ordinary means -- so if you get worn down steadily, you're still screwed, because you're exhausted and sweating and you've got the shivers. (Note: This is sort of like a weird Bizarro-world version of Wound/Vitality Points.)
c) Give Immortals Fast Healing (they've got supernatural vigor, sure, so they don't get worn down by little strikes), and allow them to spend an Action Point to heal themselves of all injuries.
Dunno. Lot of possibilities. Probably gotta figure out what works best for your game.