Why homology with coefficients?

You can find the construction of homology with general coefficients and the universal coefficient theorem in Hatcher's Algebraic Topology, which is available free from his website.

The answer to your third question is yes.

The answer to the second part of your first question is yes, especially in the case that we take $G$ to be a field, most often finite or $\mathbb{Q}$, or $\mathbb{R}$ in differential topology. Homology over a field is simple because $\operatorname{Tor}$ always vanishes, so you get e.g. an exact duality between homology and cohomology. Homology with $\mathbb{Z}_2$ coefficients is also the appropriate theory for many questions about non-orientable manifolds-their top $\Bbb{Z}$-homology is zero, but their top $\Bbb{Z}_2$ homology is $\Bbb{Z}_2$, which leads to the degree theory in Milnor you were mentioning.

Cohomology with more general coefficients than $\mathbb{Z}$ is even more useful than homology. For instance it leads to the result that if a manifold $M$ has any Betti number $b_i(M)<b_i(N)$, where $b_i$ is the rank of the free part of $H_i$, there's no map $M\to N$ of non-zero degree. This has lots of quick corollaries-for instance, there's no surjection of $S^n$ onto any $n$-manifold with nontrivial lower homology! Edit: This is obviously false, and I no longer have any idea whether I meant anything true.

But in the end $H_*(X;G)$ is more of a stepping stone than anything else; it gets you thinking about how much variety there could be in theories satisfying the axioms of homology. It turns out there's almost none-singular homology with coefficients in $G$ is the only example-but if we rid ourselves of the "dimension axiom" $$H_*(\star)=\left\{\begin{matrix}\mathbb{Z},*=0\\0,*>0\end{matrix}\right.$$ then we get a vast collection of "generalized (co)homology theories," beginning with K-theory, cobordism, and stable homotopy, which really do contain new information. In some cases, so much new information that we can't actually compute them yet!

First of all, on the level of complexes $C_n(X;A)=C_n(X)\otimes A$, but (in general) $H_n(X;A)\ne H_n(X)\otimes A$. Nevertheless, if you know ordinary homology you can compute homology with any coefficients — so these groups don't contain any really new information (see 'universal coefficient theorem' for details).

Main reason to consider (co)homology with non-trivial coefficients, I believe, that sometimes these groups (and extra structure on these groups) are easier to compute.

For example, when you compute $H_n(X;\mathbb Z/2)$ you can forget about all problems with signs etc (a concrete example: it's quite easy to compute (co)homology of $SO(n)$ with coefficients $\mathbb Z/2$ but very hard even to describe answer for ordinary (co)homology group); when you compute homology with rational coefficients, you can forget about all torsion-related phenomena.

Somewhat more advanced example: the algebra of stable cohomological operations mod p (see 'Steenrod squares' / 'Steenrod powers' ) is much easier to describe than the algebra of integral cohomological operations. (All this reminds slightly situation in number theory, where many problems are easier to solve mod p or maybe rationally than in integers.)

Also some constructions (obstructions, characteristic classes...) naturally 'live' in (co)homology with non-trivial coefficients (see e.g. 'Stiefel–Whitney classes').

Finally, (co)homology group with coefficients in a field with char 0 have different analytical description ('de Rham cohomology' etc) and (at least in some situations) some extra structue (e.g. 'Hodge structures' in cohomology of projective complex manifolds).