c. 1400, instruccioun, "action or process of teaching," from Old French instruccion (14c., Modern French instruction), from Latin instructionem (nominative instructio) "an array, arrangement," in Late Latin "teaching," from past participle stem of instruere "arrange, prepare, set in order; inform, teach," from in- "on" (from PIE root *en "in") + struere "to pile, build" (from PIE *streu-, extended form of root *stere- "to spread").
Teaching is the general word for the imparting of knowledge .... Instruction has the imparting of knowledge for its object, but emphasizes, more than teaching, the employment of orderly arrangement in the things taught. [Century Dictionary]
Meaning "an authoritative direction telling someone what to do; a document giving such directions," is early 15c. Related: Instructions.