I've independently rediscovered this formula while thinking about problem $B6$ from this year's Putnam competition $-$ I've managed to find this thread by googling "signed sums of connected graphs on signed vertices". I think my proof is different from the ones previously posted, though there is some similarity.
We prove by simple induction from $n-1$ to $n$. Let $H'_n \subset C_n$ be the set of all connected graphs $G$ in which the vertex $n$ is a leaf, i.e. has degree exactly 1. Then the graph $G' = G \setminus \{n\}$ obtained by deleting $n$ must be a connected graph on $1,\dots,n-1$, i.e. $G' \in C_{n-1}$. The mapping $G \mapsto G'$ is exactly $n-1$ to $1$: $G$ can be constructed from $G'$ in $n-1$ ways by adding one edge $(i,n)$ with $1 \le i \le n$. Finally, we clearly have $|G| = |G'| + 1$, so $(-1)^{|G|} = -(-1)^{|G'|}$. All together, we obtain $\sum_{G \in H'_n} (-1)^{|G|} = (n-1)\sum_{G' \in C_{n-1}} -(-1)^{|G'|} = -(n-1)(-1)^{n-2}(n-2)! = (-1)^{n-1}(n-1)! $
It remains to be seen that $\sum_{G \in C_n \setminus H'_n} (-1)^{|G|} = 0$, which we demonstrate by constructing a simple sign-changing involution: Suppose $G \in C_n \setminus H'_n$. Then the degree of the vertex $n$ is at least $2$ (of course it is not $0$, since $G$ is connected). Let $i,j$ be the two smallest neighbours of $n$ in $G$. Let $\sigma(G)$ be the graph obtained from $G$ by flipping the edge $(i,j)$. Clearly $|\sigma(G)| = |G| \pm 1$ has different parity, the neighbours of $n$ are unchanged so $\sigma$ is an involution, and the connectedness of the graph is independent of the existence of the edge $(i,j)$, since $i$ and $j$ are already connected via $n$. Thus the cancellation is proved.
This proof can likely be related to the proof by hierarchical trees: If we reitrate the argument, i.e. consider only
$G \in H'_n$ which map to
$G' \in H'_{n-1}$ which in turn map to
$G'' \in H'_{n-2}$ and so on - this will yield exactly graphs
$G$ which are (reversed) hierarchical trees, by Mike Spivey's argument of iterated leaves.
I also remark that I rediscovered this formula while seeking a generalization of it: namely, if $C_{n,k}$ is the set of graphs on $n$ signed vertices with exactly $k$ connected components, then the corresponding sums over $C_{n,k}$ yield the signed Sterling numbers of the first kind: $(*) \quad \sum_{G \in C_{n,k}} (-1)^{|G|} = s(n,k) = (-1)^{n-k} {n \brack k} $
Indeed, the case $k=1$ is exactly the statement for $C_n$, and the general case can be obtained from it by considering the partition of $[n]$ into connected components $I_1, \dots, I_k$, and applying the formula for connected graphs on each $I_i$. The summation over all partitions then corresponds to counting the $n \brack k$ permutations with exactly $k$ cycles by first partitioning $[n]$ into the $k$ sets $I_1,\dots, I_k$, then choosing a cycle on each set. In both computations, the summand corresponding to the partition $I_1,\dots,I_k$ is $\prod_i (-1)^{|I_i|-1}(|I_i|-1)! = (-1)^{n-k} \prod_{i} (|I_i|-1)!$
More interestingly, it seems to me that $(*)$ follows directly by the argument in Yuval's answer, applied to $C_{n,k}$ and hierarchical forests with $k$ components. Perhaps all proofs here also yield a direct proof of $(*)$ - I have not checked.
Equation $(*)$ can also be shown directly using the definition of $s(n,k)$ by $ (**) \quad x(x-1)\cdots(x-n+1) = \sum_{k=0}^n s(n,k) x^k $ This proof is more directly related to the Putnam question (in fact, it is what lead me to $(*)$). Note that the left hand side of $(**)$ is the number of ordered $n$-tuples $(a_1,\dots,a_n)$ where $a_i \in [x]$ are pairwise distinct. A different way to count these is by using inclusion-exclusion on the sets $A_{ij} = \{(a_1,\dots,a_n) \in [x]^n : a_i = a_j\}.$ It is immediate to obtain, for a given graph $G$ on $[n]$, that $|\bigcap_{(i,j)\in G} A_{ij}| = x^{c(G)},$ where $c(G)$ is the number of connected components in $G$. Note that the inclusion-exclusion is performed by summation over such graphs $G$, with weights $(-1)^{|G|}$. Equation $(*)$ is then obtained by comparing the coefficients of $x^k$ in $(**)$.