Old English steppan (Anglian), stæppan (West Saxon) "take a step," from West Germanic *stap- "tread" (cf. Old Frisian, Middle Dutch, Dutch stap, Old High German stapfo, German stapfe "footstep"), from PIE root *stebh- "to tread, step" (cf. Old Church Slavonic stopa "step, pace," stepeni "step, degree"). Originally strong (past tense stop, past participle bestapen); weak forms emerged 13c., universal from 16c. Stepping stone first recorded early 14c.; in the figurative sense 1650s. Step on it "hurry up" is 1923, from notion of gas pedal; step out (v.) is from 1907.
Old English steppa (Mercian), stæpe, stepe (West Saxon) "stair, act of stepping," from the source of step (v.). Meaning "action which leads toward a result" is recorded from 1540s. Warning phrase watch your step is attested from 1934. Step-dancing first recorded 1886.
Old English steop-, with connotations of "loss," in combinations like steopcild "orphan," related to astiepan, bestiepan "to bereave, to deprive of parents or children," from Proto-Germanic *steupa- "bereft" (cf. Old Frisian stiap-, Old Norse stjup-, Swedish styv-, Middle Low German stef-, Dutch stief-, Old High German stiof-, German stief-), literally "pushed out," from PIE *steup-, from root *(s)teu- (see steep (adj.)).
Etymologically, a stepfather or stepmother is one who becomes father or mother to an orphan, but the notion of orphanage faded in 20c. For sense evolution, cf. Latin privignus "stepson," related to privus "deprived."