Какой датчик устанавливается на робота, чтобы он мог определить, что сделал шаг?

датчик шага

По-разному. Может вообще не быть, если двигло шаговое, может быть оптрон или Холл.

Если робот колёсный - то просто датчик оборотов на колесо. Если нет - тогда акселерометр, или вообще полноценный БИНС.

Смотря какой мотор и управление.
Для шагового мотора такой датчик не нужен от слова совсем.