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).
You already probably know the advantages of thinking of homology as being a functor of $X$. By allowing an abelian group $G$ as coefficients, it becomes a functor of two variables, the space $X$ and the group $G$. Now you can exploit the $G$-functoriality as well.
For example, the short exact sequence of groups $$0 \to \mathbb Z \to \mathbb Z \to \mathbb Z/p\mathbb Z \to 0$$ (the second arrow is mult. by $p$) gives rise to the short exact sequence of cohomology groups $$0 \to H^i(X,\mathbb Z)/p H^i(X,\mathbb Z) \to H^i(X,\mathbb Z/p\mathbb Z) \to p\text{-torsion subgroup of } H^{i+1}(X,\mathbb Z) \to 0.$$ (Here I have switched from homology to cohomology, since I find that latter a little easier to think about, and easier to state these sorts of results about.)
So studying cohomology with coefficiens in $\mathbb Z/p\mathbb Z$ is closely related to studying torsion in cohomology with $\mathbb Z$-coefficients. If $p$ is a prime (which is the case I was imagining, although the above is valid for any integer $p$), then $\mathbb Z/p\mathbb Z$ is a field, and so we can investigate torsion in cohomology by studying cohomology with coefficients in a (finite) field. The latter investigation has technical advantages, e.g. Poincare duality if $X$ is a manifold.
Thinking of cohomology as a functor of $G$ as well as of $X$ leads to the idea of sheaf cohomology (a sheaf of abelian groups is something like an abelian group that can vary from point to point over $X$). The possibility of taking $G$ to be a non-constant sheaf greatly increases the flexibility of cohomology as a tool.
Another example of utility of coefficients:
If $E \to B$ is a fibre bundle with fibre $F$, and $B$ is connected and simply connected, then there is a spectral sequence (the Leray spectral sequence) $$ E_2^{i,j} := H^i(B,H^j(F,G) ) \implies H^{i+j}(E,G),$$ relating the cohomology of the base and fibre to that of the total space.
Note that even if we take $G$ to be $\mathbb Z$, the cohomology of the base has coefficients in the cohomology groups $H^j(F,\mathbb Z)$, which are likely not just equal to $\mathbb Z$.
If $B$ is not simply connected, then there is a similar spectral sequence, but the coefficients are a locally constant, but typically non-constant, sheaf on $B$.