I'm trying to prove that if the pushforward $dF$ of a smooth map $F\colon M\to N$ between smooth manifolds is zero, then $F$ is constant on each component.
It will be enough to show $F$ is locally constant, since locally constant functions on constant on connected domains. If $p\in M$, let $(U,\varphi)$ and $(V,\psi)$ be charts witnessing smoothness of $F$ at $p$, with local coordinates $(x^i)$ and $(y^j)$. If $\hat{F}$ is the coordinate representation, then we have $$ 0=dF_p\left(\frac{\partial}{\partial x^i}|_p\right)=\sum_j\frac{\partial{\hat{F}^j}}{\partial x^i}(\hat{p})\frac{\partial}{\partial y^j}|_{F(p)} $$
But the $\partial/\partial y^j|_{F(p)}$ form a basis for $T_{F(p)}N$, so it follows that $\partial\hat{F}^j/\partial x^i(\hat{p})=0$ for all $i$ and $j$. So $\hat{F}$ has vanishing Jacobian at $\hat{p}$, which is the coordinate representative of $p$. Does this imply that $\hat{F}$ is locally constant at $\hat{p}$ for some reason? I presume this is a known fact but I have a gap in my analysis.
I feel like that's the point here, but I'm not sure because for instance paraboloids have vanishing partials are their vertex, but aren't locally constant there.
You're right and it's just a consequence of the mean value theorem. If a function $f : I \to \mathbb{R}$ has vanishing derivative for some open interval $I \subset \mathbb{R}$, then for any $x_0, y \in I$, there is a $\xi \in I$ such that $f(y) = f(x_0) + f'(\xi)(y-x_0) = f(x_0)$ so we see that $f$ is constant on $I$. In your situation $\frac{\partial \hat{F}^j}{\partial x^i} \equiv 0$ on $\varphi(U)$ for all $i$ and $j$ so using the above argument in every directions and for all components of $\hat{F}$ you indeed get that $\hat{F} \equiv \hat{F}(\hat{p})$ for any $\hat{p} \in \varphi(U)$.
Note that in your example of a graph paraboloid, the differential of the function is zero only at 1 point, not in a neighborhood of that point.