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.  

Let me contrast this definition with other concepts, which I believe
should be orthogonal to being explicit.

* computational complexity: a bijection may be computable in
  polynomial time and memory, but still be not explicit.

  For example, Dyck paths of semilength $n$ with exactly one valley are
in bijection with subsets of size $2$ in $\{1,\dots,n\}$.  A
non-explicit bijection which is computable in polynomial time is to
fix an order on the Dyck paths, and an order on the subsets and match
elements with the same index.

* simplicity: a bijection may be very complicated, but still be
  explicit.

  A (biased) example is Jagenteufel's bijection between Riordan paths
and standard Young tableaux with three rows, whose row lengths are
either all odd or all even, see Algorithm 3 in
https://arxiv.org/abs/1801.03780, or Algorithm 3 in
https://arxiv.org/abs/1902.03843 for a generalisation to fans of
Riordan paths.

  Although this bijection is really complicated, it allows to deduce a
refinement of the equinumeration result, that is otherwise
unavailable.

* apparently bijective:

  The sweep maps on lattice paths were defined by Armstrong, Loehr and
Warrington in https://arxiv.org/abs/1406.1196.  It took quite a while
to show that they are bijective, see Thomas and Williams
https://arxiv.org/abs/1512.01483.  I think that the maps were
bijective already in June 2014, and did not become bijective in
December 2015, but philosophy might disagree.

  I am sure there are also examples where the only known proof of bijectivity uses enumeration, but the map itself yields other properties.

* apparently well defined:

  Consider [Prüfer's bijection][1] between $(n-2)$-tuples of integers in
$\{1,\dots,n\}$ and labelled trees on $n$ vertices.  Although not
hard to see, it is not a priori clear that given a tuple one actually
obtains a tree: from the definition of the algorithm itself one might
think that the result could be forest.

  [1]: https://en.wikipedia.org/wiki/Pr%C3%BCfer_sequence