From the OED (talking about early coaches): "boot (b). An uncovered space on or by the steps on each side, where attendants sat, facing sideways; later, a low outside compartment before or behind the body of the vehicle."
This goes back at least to the 1600s; there might be a relationship with boot-locker, perhaps where the passengers stored their boots on entering.