The story
Presumably a clipped form of cater-cornered, from cater + corner, q.v., although catty-cornered is attested earlier (1838).
Etymology from Wiktionary, CC BY-SA 4.0.
cater-corner
Today it means: At a diagonal to another; of four corners, those diagonal to another. Full definition →