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".