Ducange derives this word from Sarah (Abraham's wife); Hottinger from the Arabic saraca (to steal); Forster from sahra (a desert); but probably it is the Arabic sharakyoun or sharkeyn (the eastern people), as opposed to Magharibë (the western people —i.e. of Morocco). Any unbaptised person was called a Saracen in mediaeval romance. (Greek, Surakenos.)
“So the Arabs, or Saracens, as they are called ... gave men the choice of three things.” —E. A. Freeman: General Sketch, chap. vi. p. 117.
Source: Dictionary of Phrase and Fable, E. Cobham Brewer, 1894
More on Saracens from Fact Monster: