I would say that a bijection $\pi: A\to B$ is explicit, if for every $a\in A$ the image $\pi(a)$ can be computed without reference to $B$ itself.

In particular, I believe that one should not require that well-definedness or injectivity is obvious from the algorithm.

Unfortunately, I am unable to make the phrase 'without reference to $B$' precise.  However, to illustrate it, sorting $B$, or iterating over $B$ to find a particular object, is clearly not allowed.