The middle Dutch word “decken” meant “to cover or adorn” and came from “dec”, which originally meant any cover, such as a tarpaulin or a roof.
It was borrowed into English as a nautical term in the fifteenth century.
Although today a backyard deck might mean a wooden patio, a ship’s deck was not a floor but a roof to cover cannons.
The Christmas carol “Deck the Halls” is saying simply “cover the walls” with boughs of holly.