Latin I believe; comes from statiō which means standing still.
Like static. Or even state and of course both stationary and stationery (the latter cos it shows one's station in life ^ I think

).
According to my dictionary (which is pretty big, if that aids credibility) it was used for university bookshops, also supplying writing materials and other scholars' supplies. It was a Latin word for shopkeeper (with a fixed shop, as opposed to pedlar without one) and of course universities did use Latin in everyday life.
I have also heard that it was used for a shop set up at a staging post, or operated by the innkeeper (as it often was). They usually handled mail, which travelled by stagecoach, but I suspect the term was transferred to them from the university usage.