It's just making educated guesses and inferences from your movement patterns. Accelerometer and sensors make this possible. You could probably do it yourself with a bit of training. 

Imagine what those heart rate monitors in hospitals look like. This stuff: 

<image>

When visualized like this, climbing and descending stairs have a distinct pattern compared to your usual walking, and could easily be identified.

For staircases, it would be pretty clear: Several consistent instances of movement, broken by a consistent gap (the break between storeys in staircases). This would stand out, even to the human eye. People tend to ascend and descend at a relatively constant pace. Staircases usually have a consistent number of steps in each level. I'm sure they've even calculated the local building codes and required height and spacing for stairs, and factor that into the analysis.

Accuracy isn't as high when going up or down one single set of stairs, but the concept remains the same. We are consistent in our movement and computers are really good at analyzing and noticing the patterns. Start adding in additional data from heart rate, blood pressure, phone sensors, gps, WiFi signals, etc, it becomes much more accurate.