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.
For the case of a closed oriented surface $S$, its first Betti number $\beta_1$ and its genus $g$ are related by the equation
$$\beta_1 = 2g
$$
Those two quoted phrases therefore cannot be the same. Notice that the cut procedure in the phrase defining genus is quite precise, whereas the cut procedure defining Betti number is rather vague, and therein lies the difference. You might want to follow up the reference given in the Betti number definition, which occurs right after your quote cuts off. One traditional way to describe $\beta_1$ is as the maximal number $2k$ of simple closed curves in $S$ that can be listed as $a_1, b_1, a_2, b_2,...,a_k,b_k$ so that if $i \ne j$ then $a_i$ and $b_i$ are disjoint from $a_j$ and $b_j$, and so that $a_i,b_i$ intersect each other transversely exactly one time.
Your question also raises several other issues, and I'll treat these briefly.
The equation $\beta_1 = 2g$ that relates the first betti number and the genus can be deduced by comparing the actual definition of $\beta_1$, namely the rank of the first homology group, with the actual calculation of the first homology group of the surface (carried out by using any of the calculational procedures learned in algebraic topology). I don't think it's particularly fruitful to over-interpret the meaning of an intuitive explanation of betti number in terms of "number of holes". The purpose of that intuition is to get you started, and you could keep reading other posts on that issue if you desire, but really you should dig into the technical details of homology groups to learn what's really going on.
In particular, the relation between the Euler characteristic and the genus can again be deduced by working through the calculations of homology groups.
If you want more detail, it would be better to ask separate and more precisely worded questions, instead of lumping too many vaguely worded questions into one post.
Best Answer
The fact that the genus is an intrinsic property does not mean that one's favorite method of counting holes is an intrinsic property. Perhaps, historically or as a teaching method, counting holes can lead us to the genus, which is proved to be intrinsic by the equation $$\chi(S)=2-2g $$ and by a separate topological proof that $\chi(S)$ is intrinsic.
So, your guess about that rule is correct: don't bother trying to stretch the idea of "holes" beyond the initial intuition.