The number one reason for creaking floors, staircases and furniture is they are assembled using regular nails. The problem with regular nails is the following.
When you put load onto any board in your assembled staircase the board bends slightly and this causes it to slightly pull the nails at the places where the board is connected to other parts. After this repeats for thousand times the nails remain slightly extended out of the part and so the board is no longer tightly attached.
Now every time you put load the board bends and the walls of the nail holes rub against the nails and this causes the creaking sound. When you remove the load the board restores its original form and the same rub-and-creak process repeats in reverse.
So the bottom line is you have to reassemble the staircase using some fasteners that withstand extreme alternating load. I had great success using wood screws for furniture. One answer to this question mentions that wood screws are brittle and so maybe less reliable and so you could use some advanced nails. Anyway you have to use fasteners with extreme resistance to pulling out.
You likely don't need to dissassemble the staircase completely. In most cases adding new fasteners or replacing old ones one-by-one will be sufficient.