The Dictionary of American Regional English, volume III I-O, has this on page 877:
in phr. on line: In line. chiefly NYC, nNJ
1958 Francis Structure of Amer. Engl. 518, New York City and Hudson Valley...Morphology and Syntax. [H]e lives in King Street...we stood on line.
My gut feeling is that this is from New York's German immigrants. We also say "on the avenue." Perhaps the following (available electronically) is an early example of this type of speech:
A VAGABOND IN NEW YORK
by Oliver Madox Hueffner
New York: John Lane Company
(Binghamton, NY: The Vail-Ballou Company)
You would say "on Third Avenue," by the way, and never "in."