They booked.

I know what it means ( they left quickly with out notice, generally criminals)but where has this originated?

Just a guess:
The mode of transport has been dropped from the sentence.
"They booked.. (a flight for Yemen)."

Maybe, but I generally understand it to mean on foot

Yes, I agree, on foot.
I guess over time the usage has expanded to include walking away or running. But generally it means to "move away from quickly" either by foot or mechanical means.
This is a guess as I have no sources at all to confirm or deny my theory on "book".

For what it's worth, in my neck of the woods, "booked" has always been considered a faster form of "boogied," as in "I boogied, but they booked." Boogied implies a bit more of a casual exit; when you book, you high-tail and scram...

Thinking more about it, I'd guess "booked" derives from "boogie" via lame white-guy attempts to affect a hip, inner-city lingo (that's my lame white-guy opinion, anyway). I would guess you never hear someone say "Let's book," and you'd not likely hear someone contract "boogied" to say "We booged." If they did, you'd hear "We booked"....