I think it goes back to Hansel & Gretel: leaving bread crumbs along the trail they walked so they could find their way back. This notion of handing over a token to a service who would then give it back later (think dry cleaning receipts) is a similar idea. This mutated into "cookie crumbs" and finally just "cookies" ...
I think.
/jordan