How is the topological $Z_2$ invariant related to the Chern number? (e.g. for a topological insulator)

The answer of David Aasen is correct, but let me add some comments which connect to your question of the relation of between the $\mathbb Z_2$ invariant $\nu$ and the first Chern-Number $C_1$.

Such a relation does not exist unless you require some extra symmetry than the generic symmetries usually required in the classification of topological insulators (such as time-reversal invariance in this case). Say the Hamiltonian is invariant under spin rotations along the $z$-axis (so a $U(1)$ subgroup of $SU(2)$ in left invariant), then the Hamiltonian can be block-diagonalized as

$H = \begin{pmatrix} H_\uparrow & \\ & H_\downarrow \end{pmatrix}, $

where the indices refer to spin-up and down degrees of freedom. Due to time reversal symmetry we have that $H_\downarrow(k) = H^*_\uparrow(-k)$. The system now consist of two copies of Quantum Hall effects with counter propagating edge states of opposite spin. As Davis Aasen says, the chern number is zero $C_1 = C_1^\uparrow + C_1^\downarrow = 0$. The difference however, the "spin Chern number", $C_1^\uparrow - C_1^\downarrow = 2C_{spin}$ can be non-zero and can be calculated by the Chern-numbers of the spin up/down sectors. As long as $S_z$ is preserved the spin Chern-number can be any integer $C_{spin}\in\mathbb Z$.

But if we add off-diagonal elements, and thus break the rotation symmetry along $z$, the invariant breaks down to $\nu = C_{spin}\,\text{mod}\,2\in\mathbb Z_2$ (as was shown by Kane and Mele). So topological trivial/non-trivial phases are characterized by even and odd spin-Chern numbers $C_{spin}$, not the original Chern number $C_1$. This however only makes sense when you have this extra symmetry.

For a time reversal invariant bloch hamiltonian (such as in a $\mathbb{Z}_2$ topological insulator) the Chern number is always zero.

The topological invariant $\nu = 0,1$ classifies the insulator as trivial or topological. This can be found by counting the number of times the surface energy bands intersect the Fermi energy mod 2 as you mentioned above.

For a reference see the RMP by Hasan and Kane, http://rmp.aps.org/pdf/RMP/v82/i4/p3045_1 Sections II.B.1 and II.C.

I hope this was helpful. I am trying to learn about these topics as well.