“Natural” bijection in category theory?

In this context, yes, because the bijection between $\mathcal{P}(X)$ and $2^X$ is natural category-theoretically (it's usually an exercise you do when you are learning category theory), while if you just take $Z$ of the same cardinality, then naturality doesn't even make sense because on one side you have a functor ($X\mapsto \mathcal{P}(X)$) and on the other side you have a single object $Z$, so it doesn't even make sense to speak of naturality.

However if you restrict to a single $X$, then there are two categories you may want to have a look at : the trivial category on $X$, that has only $id_X$ as morphism, or the full subcategory of $\mathbf{Set}$ on $X$, which has as morphisms $\hom(X,X)$. In the first case, the functors $X\mapsto \mathcal{P}(X)$ and the constant functor $X\mapsto Z$ will be naturally isomorphic; in the second case, the functor $X\mapsto \mathcal{P}(X)$ acting the usual way on maps, and the constant functor $X\mapsto Z$ aren't naturally isomorphic - though there is a way to act on arrows to have a functor $X\mapsto Z$ that is naturally isomorphic to $X\mapsto \mathcal{P}(X)$.

What this shows is that to make sense of what "natural" means you have to be careful about what the categories involved are; and how the functors act, not only on objects, but also on arrows.

Here's a possible interpretation: take the contravariant functor

$$ \newcommand{\c}[1]{\mathbf{#1}} \newcommand{\cop}[1]{\c{#1}^{op}} \newcommand{\parts}[1]{\mathcal{P}(#1)} \newcommand{\2}[1]{2^{#1}} \begin{align} \parts{-} : &\ \c{Set} \longrightarrow \cop{Set} \\ & X \longmapsto \parts{X} \\ & \downarrow^f \ \mapsto \ \uparrow^{\parts{f}} \\ & Y \longmapsto \parts{Y} \end{align} $$

with $\parts{f}(A) = f^{-1}(A)$. Using your notation, there is another contravariant functor in $\c{Set}$ that can be defined as $\2{-} := \hom_{\c{Set}}(-,\{0,1\})$. To formalize your intuition, one would like to have a natural transformation between these.

In fact, we actually have a natural isomorphism defined by: $$ (\eta_X : \parts{X} \to 2^X)_{X \in \c{Set}}, \quad \eta_X(A)(x) = \cases{1 \text{ if } x \in A \\ 0 \text{ otherwise}} $$

which is to say that $\eta_X(A) = \chi_A \in \hom(X,\{0,1\}) = \2{X}$. In effect, $\eta$ is natural because given an arrow $f :X \to Y$ in $\c{Set}$, $$ \eta_X\parts{f}(A) = \eta_X(f^{-1}(A)) = \chi_{f^{-1}(A)} = \chi_Af = f^*(\chi_A) = \2{f}(\eta_X(A)) $$

with $2^f = f^*$ being the precomposition of $f$, i.e. $f^*(g) := gf$. Finally, $\eta$ is an isomorphism as each arrow $\eta_X$ is

• injective because if $A \neq A' \in \parts{X}$ then $\eta_X(A)(z) \neq \eta_X(A')(z)$ for $z \in A' \triangle A$.
• surjective because given $s : X \to 2$, then $s = \chi_{s^{-1}(1)} = \eta_X(s^{-1}(\{1\}))$.

and isomorphisms in $\c{Set}^{op}$ are bijections.