Apparently not mentioned yet, though surely not new:
use the quadratic equation satisfied by the generating function.
Since we look for $n+1$ to be a power of $2$, we shift the index by $1$
and consider
$$
F = \sum_{n=1}^\infty C_{n+1} x^n = x + x^2 + 2 x^3 + 5 x^4 + 14 x^5 + 42 x^6 + 132 x^7 + 429 x^8 + \cdots.
$$
Then $F = x + F^2$.  Instead of solving this quadratic equation,
apply it recursively ${} \bmod 2$.  Recall that for each $r=1,2,3,\cdots$
we have the congruence $(a+b)^{2^r} \equiv a^{2^r} + b^{2^r} \bmod 2$
(proof: induction, the case $r=1$ being 
$(a+b)^2 = a^2 + 2ab + b^2 \equiv a^2+b^2$.  We obtain:
$$
\begin{array}{rl}
F \; = \!\! & x + F^2 \cr
 = \!\! & x + (x+F^2)^2 \equiv x + x^2 + F^4 \cr
 = \!\! & x + x^2 + (x+F^2)^4 \equiv x + x^2 + x^4 + F^8 \cr
 = \!\! & x + x^2 + x^4 + (x+F^2)^8 \equiv x + x^2 + x^4 + x^8 + F^{16} \cr
 = \!\! & \cdots \cr
 \equiv \!\! & x + x^2 + x^4 + x^8 + x^{16} + x^{32} + x^{64} + \cdots \cr
\end{array}
$$
so indeed $C_n$ is odd if and only if $n+1$ is a power of $2$, **QED**.