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. More precisely, suppose that $A$ and $B$ are not known, but only an element $a\in A$, then it should still be possible to construct $\pi(a)$.
In particular, sorting $B$, or iterating over $B$ to find a particular object, is not possible with this definition.
On the other hand, this allows algorithms whose well-definedness or injectivity is not obvious from the algorithm. I think that this is in fact desirable.