http://www.onion-router.net/History.html
1995: Initial work on Onion Routing begins, funded by ONR.
http://cypherpunks.venona.com/
grep onion cyp-1993.txt
# For example, Eric Messick calls his things "onions," suggesting multiple
Interesting … the ISO NLSP-C did not call it’self an ‘opinion’, but about 1993 it supported multiple tunnel encapsulations that could be used for anonymity services ( https://goo.gl/CG9Koc ). It was derived from the 89 vintage NSA defined SP3-C protocol ( http://goo.gl/QEp67F ).
"(For example, Eric Messick calls his things "onions," suggesting multiple layers of "return postage guaranteed" envelopes. This may be a great idea, and even a great name (which we may all be using in 5 years),"
Also, the idea of multiple, nested, encrpyted 'envelopes' that contain routing information is routinely mentioned at that time, if I'm not mistaken.