The way stairs work is not intuitive.
A downstairs must be paired to an upstair on the level below. An upstair must be paired to a downstair on the level above. Therefore, if you dig out a downstair to go down one z level, you must on the next z level down dig an upstair.
You can dig a downstair on the surface, then dig out as many up/downstairs as you like to the bottom of the world, but it must start with a downstair.
If you dig an up/down stair into a wall, you can either go up or down or both. If you wish to create a staircase where you have already dug, you must build a staircase following the above rules.
So, either designate stairs for digging or build them from the construction menu. Upstairs must be matched to downstairs. Up/down stairs work either way. Constructed stairs follow the same rules as other constructions in placement. So if you want to build a stairway leading to the top of your wall, on the first z level (the bottom of the wall) build an upstair. Then, directly above that upstair, build a downstair. Don't try to build the downstair on the z level above you and then build the upstair, you'll get an error (unless there are floors, in which case it might or not work depending on path access to material)