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.