From Halopedia, the Halo wiki
Caledonia was one of the six continents on the planet Arcadia, a human colony in the Procyon system governed by the Unified Earth Government. It was abandoned after the Battle for Arcadia in 2531 and destroyed by the Covenant in the Second Fall of Arcadia in 2549.
There was four existing provincial regions on the continent.
It is most likely named after Caledonia, the Latin name given to Scotland by the ancient Romans. The four provincial regions also share their names with places in Scotland.