Old English stelan "to commit a theft, to take and carry off clandestinely and without right or leave" (class IV strong verb; past tense stæl, past participle stolen), from Proto-Germanic *stelanan (source also of Old Saxon stelan, Old Norse, Old Frisian stela "to steal, to rob one of," Dutch stelen, Old High German stelan, German stehlen, Gothic stilan "to steal"), from PIE *stel-, possibly a variant of *ster- (3) "to rob, steal."
"The notion of secrecy ... seems to be part of the original meaning of the vb." [OED]. Intransitive meaning "to depart or withdraw stealthily and secretly" is from late Old English. Most IE words for steal have roots in notions of "hide," "carry off," or "collect, heap up." Attested as a verb of stealthy motion from c. 1300 (as in to steal away, late 14c.); of kisses from late 14c.; of glances, sighs, etc., from 1580s. The various sports senses begin 1836. To steal (someone) blind first recorded 1974.
1825, "act or case of theft," from steal (v.). Meaning "a bargain" is attested by 1942, American English colloquial. Baseball sense of "a stolen base" is from 1867.