How does damage work? I mean is physical stress like hit points, or health levels?
Stress isn't really damage - it's fatigue, stress (as in tension, pressure, or strain) buildup, and simply the ability to concentrate or jump out of the way. This is why you recover it once a scene ends.
What about consequences? Critical damage?
Consequences are damage. This doesn't mean you're automatically hit by a bullet if you're shot - taking a minor consequence might be a
Pulled Hamstring as you dove behind cover as your opponent pulled the trigger. Of course it might also be a
Grazing Flesh Wound. Whatever makes sense in the narrative you're building.
How does something like recovery powers affect it? Supernatural recovery is more important cause my character has that.
Recovery powers affect how fast and, in some ways, how many consequences you can take. Inhuman Recovery allows you to a) recover without medical attention,* b) completely regenerate any damage, c) heal faster than normal (mild heals immediately, moderate as if mild, etc), d) allows more physical endurance, and e) allows you to shrug off a mild consequence in combat. Do note one limitation, this only applies to physical damage.
*Except extreme consequences.