From http://www.etymonline.com/index.php?l=s&p=41
From http://www.takeourword.com/Issue009.html
step- O.E. steop-, with connotations of "loss," in combinations like steopcild "orphan," related to astiepan, bestiepan "to bereave, to deprive of parents or children," from P.Gmc. *steupa- "bereft" (cf. O.Fris. stiap-, O.N. stjup-, Swed. styv-, M.L.G. stef-, Du. stief-, O.H.G. stiof-, Ger. stief-), lit. "pushed out," from PIE *steup-, from base *(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. L. privignus "stepson," related to privus "deprived."
From http://www.takeourword.com/Issue009.html
The prefix step- used in this sense is Middle English, derived from Old English steop-. The Old English form is cognate with similar forms in many of the Germanic languages: Old Frisian stiap-, Middle Low German stef-, Middle and modern Dutch stief-, Old High German stiof-, Old Icelandic stjup-, Swedish styv-, Old Danish stiup-, and Norwegian ste-. The Old English form comes from steopcild ("stepchild"), which meant "orphan". The steop- prefix comes from Old English astiepan/bestiepan "bereave" (with cognates in Old High German arstiufen/bestiufen). The sense is that an orphan is bereaving his lost parent(s). Before 800, stepfather/stepmother meant "one who becomes a father/mother to an orphan", and stepson/stepdaughter meant "an orphan who becomes a son/daughter by the remarriage of a parent".