Here's the problem I'm working on: Let Σ be a connected closed surface. Assume that Σ is not homeomorphic to $S^2$ or $RP^2$ Show that for any integer n ≥ 2, Σ has a connected n-fold regular cover.
By the Classification Theorem, Σ is either $\#_n T^2$, a connected sum of n toruses, with n > 0. or Σ is $\#_m RP^2$ a connected sum of m real projective planes with m > 1.
For the torus and the klein bottle case, example 1.42 in Hatcher's Algebraic Topology helped me a bit. I think this is about finding subgroups of the group of deck transformations of the universal cover. So for the torus, if we want an index n subgroup, we can use the subgroup $(x,y) \mapsto (x + v, y + nu)$ where $u,v \in \mathbb{Z}$. This will correspond to an n-fold cover of the torus, if we quotient the universal cover by that subgroup. I'm not sure about the case of the Klein bottle. For all other cases I am really not sure. Perhaps I can use an inductive argument. Any advice or help is greatly appreciated.
I'm going to answer your question only for the closed oriented surface $\Sigma_g$ of genus $g$, where it has a pretty simple answer, based on covering space theory and group theory.
Start from the presentation you gave in your comment $$\pi_1(\Sigma_g) = \bigl\langle a_1,b_1,...,a_g,b_g | \prod_{i=1}^g [a_i,b_i] \bigr\rangle $$ Consider $\mathbb Z/n\mathbb Z$, the cyclic group of order $n$ with generator denoted $1 \in \mathbb Z / n \mathbb Z$. Define a homomorphism $f : \pi_1(\Sigma_g) \to \mathbb Z / n \mathbb Z$ by assigning the value $f(a_i)=f(b_i)=1$ to each generator. Since $\mathbb Z / n \mathbb Z$ is abelian and the relator $\prod_{i=1}^g [a_i,b_i]$ is in the commutator subgroup of the free group generated by the $a_i$'s and $b_i$'s, this assignment does indeed extend to a homomorphism. Since $1$ generates $\mathbb Z / n \mathbb Z$, this homomorphism is surjective. It follows that its kernel $K = \text{kernel}(f)$ is a normal, index $n$ subgroup of $\pi_1(\Sigma_g)$. And from the classification of covering spaces, it follows that there exists a degree $n$ regular covering map $$X \mapsto \Sigma_g $$ such that the image of $\pi_1(X)$ in $\pi_1(\Sigma_g)$ is equal to $K$.
Let me comment briefly on the "non-orientable genus $m$ surface" which I'll denote $P_m$ and whose fundamental group has presentation $\pi_1(P_m) = <a_1,...,a_m | \prod_{i=1}^m a_i^2>$, you must similarly find some homomorphism from $\pi_1(P_m)$ onto some finite group of order $n$, for any given value of $n$. But now the relator is not in the commutator subgroup, so there's little to be gained by mapping the generators $a_i$ to some abelian group.