I recently bought a house where the staircase running down into the garage has gaps between the treads and the edges. They look as if they are about to fall. It would make sense to me that this could happen if the right edge (the edge away from the wall) were loose... but that doesn't appear to be the case. In the pictures you can see that some of the stairs have a space on the left, one has it on the right.
(click for full size)
How do I go about fixing this?

