Since holographic theories are non-local by definition, how is this principle implemented?
Naively, it seems to me it is not, at least, in some sense.
I would appreciate an explanation as simple as possible.
I wouldn't say that "holographic theories are non-local by definition". On the contrary, in AdS/CFT the CFT is completely local and satisfies cluster decomposition.
The cluster decomposition property in AdS can be proved using the CFT bootstrap for all CFTs in $d > 2$ (see http://arxiv.org/abs/arXiv:1212.3616, the proof only requires CFT `axioms', i.e. unitarity and crossing symmetry). In the CFT it amounts to a statement about the large angular momentum limit of the OPE of pairs of operators. This translates into the statement that any two "blobs" in AdS can be set to orbit each other, and at large angular momentum ~ large separation, the blobs become independent. So at distances large compared to the AdS scale, all theories of quantum gravity in AdS$_D$ with $D > 3$ are local.