When I walk down the stairs, where does my potential energy actually go?

It becomes heat, in your muscles, and that is the whole answer: but the mechanism is more interesting than the destination.

On each step down, you fall a short distance and gravity does work on you, which would speed you up. You do not speed up, so something removed that energy. That something is your leg muscles contracting while being lengthened, your quadriceps are pulling to hold you up at the same time as the knee is bending. This is called an eccentric contraction, and it is your body acting as a brake.

A brake turns motion into heat. A car's discs get hot; your thigh muscles do the same thing on a smaller scale. Some of the energy also goes into deforming tendons and cartilage and into sound.

So the energy is not vanishing and it is not being stored. It is being deliberately destroyed, by you, on every step, to stop you accelerating down the stairs.

Deliberately destroyed by you on every step. That framing is worth the whole thread.

Question 2 is where it gets counterintuitive, and it is worth its own explanation because it feels like a contradiction.

Going down is less metabolically costly: you burn fewer calories per minute than going up, and if you measured oxygen consumption it would be clearly lower. So in the energy-budget sense it is easier, and that matches the intuition that you are releasing energy rather than spending it.

But eccentric contractions are unusually damaging to muscle fibres. Holding a load while lengthening produces more microscopic damage than shortening under the same load. That is why walking downhill for an hour leaves you with sore thighs two days later while walking uphill for an hour leaves you tired the same evening and fine afterwards.

So "tiring" is doing two jobs in your question. Downhill is cheaper in fuel and harder on the tissue. Both are true and they are different currencies.

On question 3: in a human, essentially not.

Muscles have some elastic recovery, tendons store and return energy, which is what makes running efficient and why a bouncing gait costs less than it should. But that works over a bounce, in fractions of a second. Over a staircase descent, at walking pace, with a deliberate pause on each step, there is nothing to bounce back into.

Where it is recoverable is in machines that were built for it. Regenerative braking in an electric vehicle is exactly your question solved: instead of turning the descent into heat in the brake discs, the motor runs as a generator and puts it in the battery. Lifts do the same thing with counterweights, which is the older and simpler answer - the descending car raises the counterweight rather than heating anything.

Your body is the version without the generator, so the heat is the end of the line.

Small addition that makes the numbers concrete, because "it becomes heat" can sound like a technicality rather than a real quantity.

An adult descending one storey releases roughly the energy of a small biscuit. Descend a tall building's worth of stairs and it adds up to a meaningful amount of heat dumped into your legs, which is part of why long descents make you warm even though you are working less hard than on the way up.

Hikers know this from the other direction: the descent is when you take a layer off, not the climb.