The story
The original sense of fast in this term is the "firmly gripped or anchored" sense, thus as if stuck fast (embedded firmly) in sleep, but the homonymy with fast as in "quickly" happens to dovetail with the fact that a very tired person will archetypally fall asleep quickly, which tends to color this term with a connotation of falling asleep both quickly and deeply.
Etymology from Wiktionary, CC BY-SA 4.0.