The word seal, according to the Oxford English Dictionary, has been in use since the 1200s:
A device (e.g. a heraldic or emblematic design, a letter, word, or sentence) impressed on a piece of wax or other plastic material adhering or attached by cords or parchment slips to a document as evidence of authenticity or attestation; also, the piece of wax, etc. bearing this impressed device.
In modern (legal) practice the seal is often represented by a coloured wafer following the signature of each of the parties.
Leaden seals were used by the Popes, the Eastern Emperors, and certain other high dignitaries.
So people literally put seals on deals; this was the older form of certifying a document. Now, as the OED says, there are still seals in use--represented by a colored wafer. I am not sure in how many countries this is practiced, but it seems that now there are both literal seals (the wafers, though they are not necessarily imprinted wax any more) and metaphorical seals (to say you "sealed the deal" even though there aren't seals impressed on them).