I think the easiest strategy is to just use an invisible ramp for your avatar to walk up rather than the actual geometry of the stairs. In a lot of (even modern) games if you look closely the feet don't match up with stairs very well at all... in fact if they did, it would probably be more frustrating than useful as it would take longer and feel more clunky to get up the stairs in a fast paced game.
I found an interesting discussion on it here.
Generally in FPSes, this is done how Macada suggests.
When you hit a "wall", you check for a collision at the character's "step height up + step distance forward" (let's call this point "step destination") and if there's no collision, then you've got a step, so you check for the step height by casting down from "step destination." Then you can translate/interpolate your character to "step destination", either by going up then forward, or a simpler diagonal translation, supported by a "step walk" animation.
You can use the same method for climbing/mantling onto objects (like boxes), by checking "climb height up + step distance forward" as a "climb destination" and using a "climb" animation instead of a "step walk."
A much easier way, especially if you're using physics and a "rolling" character collision mesh, is to use an invisible ramp for stairs instead