$\textbf{Solution}$

John sends the box containing the gift with one of his locks. Upon receiving, Mary attaches one of her locks to the box and sends it back to John. John then removes his lock and sends the box back to Mary. At this moment, the box is locked only by Mary's own lock. Done.

$\textbf{Note}$

This brain teaser has a background context in cryptography which can be used to send secured electronic messages between two parties over an insured communication channel. In this case, John and Mary do not know whether someone may try to check what is inside the box during the transition.