Определение местонахождения + акселерометр в телефоне + математика.
Первое определяет, что вы действительно двигались, а не играли в боулинг на телефоне. Второе определяет, что телефон двигался. Третье определяет, что ваша скорость не привышает скорости человека.
Чисто теоретически (ака я не проверял), если вы будете сидеть в машине, трясти телефон и ехать со скоростью пешехода, то вам засчитаются шаги.
Немного добавлю к предыдущему ответу. Акселерометр, он же инерционный датчик достаточно точная штука. Энтузиасты давно померили типичные сигналы при ходьбе. Наиболее достоверная информация получается, если телефон находится на груди (нагрудном кармане), о вот специализированные спортивные трекеры - лучше на поясе.
Чисто логически. В телефоне ещё есть gps навигатор который может измерить скорость движения.
Таким образом можно отличить ходьбу, бег от автомобиля