My suggestion has quite some overlap with other comments and also @gowers answer:
Let $A$, $B$ be two sets. An explicit bijection between $A$ and $B$ is a deterministic algorithm taking elements of $A$ as input and for which outputs are elements of $B$, such that an analysis of the algorithm yield its bijectivity.
Several notes:
In most cases I have been looking at, the sets $A$ and $B$ were finite.
A typical way of satisfying this criterion is to provide two deterministic algorithms $A \to B$ and $B \to A$ and showing that they are inverses of each other. Or showing that both are injective. I would also call this "explicit" though one might need to slightly reword to include this situation.
I did not include anything about complexity of the algorithm because I do not think its actual computation time is relevant for it being "explicit".
I have often seen the following relaxation, namely that one knows already that $|A| = |B|$, and only deduces injectivity or surjectivity from the algorithm. The problem with this relaxation is that it would allow just listing the elements of both sets...