When I was taught the classification theorem, my professor emphasized being able to compute the Euler characteristic, and his favorite examples that he set as exercises were Seifert surfaces.
For example, you can try to compute the Euler characteristic of the Hopf link: http://en.wikipedia.org/wiki/File:Hopf_band_wikipedia.png.
Or something weirder, like this surface: http://en.wikipedia.org/wiki/File:Borromean_Seifert_surface.png
Both of these images are found in the Wikipedia article for Seifert surfaces. You could easily draw more complicated Seifert surfaces, and their Euler characteristics are not so obvious to compute. The easiest way to compute the Euler characteristic of these two surfaces is to use the inclusion-exclusion principle for Euler characteristic:
$$ \chi(A\cup B) = \chi(A) + \chi(B) - \chi(A\cap B).$$
This lets you decompose the surface into more manageable objects, like disks, lines, and points, for which you should have the Euler characteristic already. So Euler characteristic becomes a recursive calculation.
You can determine orientability of these surfaces fairly easily. Consider a planar projection of the Hopf link surface: it is just the Hopf link, with the region consisting of the surface marked (perhaps shaded). Imagine you color the regions of the Hopf link with black and white, like so: first color any region black. Move to a region neighboring the first region, i.e. separated by a crossing of the link (a twist), and label that region white. Then repeat, switching color each time you move across a twist. If this coloring is consistent, then the surface is orientable. Otherwise, it is non-orientable. So the Hopf link is easily shown by this algorithm to be orientable; on the other hand, the Seifert surface of the trefoil knot is not orientable.
Finally, the number of boundary components is trivial to count.
Once you have all these ingredients, you can use the classification of surfaces with boundary to see what the surface is. I encourage using the Seifert surface of a trefoil to highlight the non-orientable case.
Another way to use the classification theorem is for polygonal representations of surfaces, for example http://en.wikipedia.org/wiki/File:KleinBottleAsSquare.svg. If you have a representation of a surface as a disc with certain pairs of sides identified, then you can easily find its Euler characteristic via the formula $$\chi = V-E+F.$$
Here we need to determine $V$, $E$, and $F$. $F=1$ if we're only considering one disc, since it's the only $2$-dimensional component. For $E$, go around the boundary of the disc and count the number of edges, with identified edges counting once. For $V$, do the same, keeping track of which vertices end up identified. For the Klein bottle example in the picture, we have $F = 1$, $E = 2$, and $V = 1$, so the Euler characteristic is $1-2+1 = 0$. The Klein bottle has no boundary, so the classification theorem states $0 = 2-2g$, so $g=1$. Hence the Klein bottle is closed and nonorientable with genus $1$, which determines its homeomorphism class.
Strictly speaking, this is sort of a special case of surfaces with boundary: the number of boundary components is the number of nonidentified edges. But in any case, this gives you an easy way to generate complicated surfaces with easily computable classifications: take some $n$-sided polygon with $n$ as large as you want, arbitrarily put orientations on the edges, identify pairs of edges, and get to work computing $V$, $E$, and $F$. The surface is non-orientable if there is a pair of identified edges both oriented clockwise or counterclockwise around the disc: basically, if edges can be oriented $+$ (clockwise) and $-$ (counterclockwise), then a non-orientable pair is $++$ or $--$. So orientability is a simple check as well. Find the number of boundary components, and now you have the Euler characteristic, number of boundary components ($0$ if you just make sure all edges are identified with another; you'll need an even-sided polygon to do this), and the orientability of the surface, everything you need to compute the genus. Hence you can classify all such surfaces.
In my answer below, I was implicitly assuming that the covering on the boundary was trivial. As Mike Miller points out below, this is not necessarily the case. See his comments for more details.
Denote the closed orientable surface of genus $g$ with $b$ boundary components by $\Sigma_{g, b}$, and the closed non-orientable surface of genus $g$ with $b$ boundary components by $S_{g,b}$. Recall that $\chi(\Sigma_{g,b}) = 2 - 2g - b$ and $\chi(S_{g,b}) = 2 - g - b$.
If $p : M \to N$ is a covering map between manifolds with boundary, then it restricts to a covering map $p|_{\partial M} : \partial M \to \partial N$ of the same degree. So if $p : \Sigma_{g,b} \to \Sigma_{g',b'}$ is a degree $k$ covering map, then $b = kb'$. Moreover,
\begin{align*}
\chi(\Sigma_{g,b}) &= k\chi(\Sigma_{g',b'})\\
2 - 2g - b &= k(2 - 2g' - b')\\
2 - 2g - kb' &= k(2 - 2g' - b')\\
2 - 2g &= k(2 - 2g')\\
\chi(\Sigma_g) &= k\chi(\Sigma_{g'}).
\end{align*}
The converse is also true. That is, if $\chi(\Sigma_g) = k\chi(\Sigma_{g'})$ and $b = kb'$, then there is a degree $k$ covering map $\Sigma_{g,b} \to \Sigma_{g',b'}$. To see this, note that if $\chi(\Sigma_g) = k\chi(\Sigma_{g'})$, then there is a degree $k$ covering map $p : \Sigma_g \to \Sigma_{g'}$; see this answer. If $D \subset \Sigma_{g'}$ is the interior of a closed disc in $\Sigma_{g'}$, then $p^{-1}(D)$ is a disjoint union of the interiors of $k$ disjoint closed discs in $\Sigma_g$. So if $D_1, \dots, D_{b'}$ are the interiors of $b'$ disjoint closed discs in $\Sigma_{g'}$, then $p^{-1}(\Sigma_{g'}\setminus(D_1\cup\dots\cup D_{b'})$ is $\Sigma_g$ with $kb' = b$ interiors of disjoint closed discs removed, i.e. $\Sigma_{g,b}$. Therefore the restriction of $p$ to $\Sigma_{g,b}$ is a degree $k$ covering $\Sigma_{g,b} \to \Sigma_{g',b'}$.
Likewise, $\Sigma_{g,b}$ is a $k$-sheeted covering of $S_{g',b'}$ if and only if $\chi(\Sigma_g) = k\chi(S_g)$, $b = kb'$ and $k$ is even. Note that $k$ must be even as any orientable covering of a non-orientable manifold must factor through the orientation double cover.
Therefore, we have the following complete list of coverings:
- $\Sigma_{5,4} \to \Sigma_{5,4}$ of degree one,
- $\Sigma_{5,4} \to \Sigma_{3,2}$ of degree two,
- $\Sigma_{5,4} \to S_{6,2}$ of degree two,
- $\Sigma_{5,4} \to \Sigma_{2,1}$ of degree four, and
- $\Sigma_{5,4} \to S_{4,1}$ of degree four.
Best Answer
Here is a proof of equivalence of 1, 3 and 4. Below, $S$ is a compact connected surface without boundary.
Definition. A maximal cut in $S$ is a 1-dimensional submanifold $L\subset S$ such that $S\setminus L$ is connected and contains no nonseparating simple loops. The latter condition just means that $S\setminus L$ is the 2-dimensional sphere with $q=q(S,L)$ points removed. (To see the latter, you can use the classification of compact surfaces.) In particular, $\chi(S_L)=2-q$.
Let $L$ be a maximal cut in $S$ and let $S_L$ denote the surface with boundary such that $S_L\setminus \partial S_L$ is homeomorphic to $S\setminus L$. Then $S$ can be reconstructed from $S_L$ as follows: represent $\partial S_L$ as a disjoint union of circles: $$ C_1\cup C_1' \sqcup ... \sqcup C_{n}\sqcup C_n' \cup A_{1} \sqcup ... A_m, $$ $q=2n+m$. Identify each $C_i$ to $C_i'$, $i\le n$ via a homeomorhism and identify each $A_i$ to itself via an antipodal map of the circle. The space $S_L/\sim$ equipped with the quotient topology is homeomorphic to $S$.
Using this, we can compute the Euler characteristics: $$ \chi(S)= \chi(S_L)= 2-q. $$ To see the first identity, triangulate $S_L$ so that the identification maps of the boundary are simplicial and just count (with the usual sign) the simplices in $S$ using simplices in $S_L$.
In particular, we see that $q$ is independent of the maximal cut. Moreover, this shows that 1 is equivalent to 4 (orientation is irrelevant). To prove equivalence of 1 and 3 in the non-orientable case, note that we can obtain $S$ from the surface $S_L$ (which is the sphere with $q$ holes) by adding a cross-cap to each hole ($q$ cross-cups in total). In the more modern terminology, we represent $S$ as the connected sum of $q$ projective planes. Equivalently, $S=S_L/\sim$, where we set $n=0, m=q$ holes with my notation above.
As for references, you can use Massey's "A basic course in Algebraic Topology". Another thing I am sure is this: There is no document confirming a consensus of topologists on this matter.