Representing a Multiple of the Fundamental Class of a Surface Let us denote a connected, oriented surface of genus $g$ by $\Sigma_g$. It is easy to see that if we have a map of degree $1$ from $\Sigma_g$ to $\Sigma_h$ then $g\geq h$. 
Suppose now that $g\geq 2$ and fix a $k\in \mathbb{Z}$. Consider the following question: What is the minimal Euler characteristic of a surface $\Sigma_h$ such that there exists a map $f\colon\Sigma_h\to\Sigma_g$ such that $f_*([\Sigma_h])=k[\Sigma_g]$. My intuition tells me that the minimal Euler characteristic case is represented by a $k$-fold covering i.e. the minimal Euler characteristic should be $k(2-2g)$, but I have a hard time proving this.
Edit: Mikes answer is great, but the both us are interested in a more elementary proof.
 A: Yes, the minimal $h$ with a degree-$k$ map $\Sigma_h \to \Sigma_g$ is that with $2 - 2h = k(2 -2g)$; that is, with $h = kg - k +1$.
Let $M$ and $M'$ be closed surfaces. Given a compact submanifold with boundary a single circle in $M$, collapsing it to a point gives a surface $Q$ and a map $\pi: M \to Q$ of degree 1. This is called a pinch map. A map which is a covering map away from a finite set is called a branched cover.
If $f: M \to M'$ is a map of nonzero degree, the main result of this article of Edmonds is that there is some pinch map $\pi: M \to Q$ and some branched cover $\beta: Q \to M'$ so that $f$ is homotopic to $\beta \pi$.
Clearly $\pi$ only increases the genus of your domain (effectively, $\pi$ collapses a connnected summand). So it suffices to answer your question in the case of branched covers. 
Coming to save the day is the Riemann-Hurwitz theorem, which asserts the following. If $\beta: Q \to M'$ is a branched cover, the local form in $Q$ of the "bad points" where your map is not a cover is given by the map $z \mapsto z^n$ on the disc $D^2$; the map is $n$-to-$1$ at that point. Writing $P$ for a generic "bad point", we write $e_P$ for the corresponding $n$ there. The assumption that $P$ is a bad point means that $e_P > 1$.
Now the Riemann-Hurwitz theorem gives $$2g(Q) = 2(1-k+g(M')) + \sum_P (e_P - 1).$$ Because the final term is non-negative (possibly zero, if $\beta$ was an honest cover), we have $$g(Q) \geq 1 - k + g(M'),$$ which is precisely the desired inequality for branched covers. 
A: I wouldn't call this elementary and it does rely on hyperbolic geometry, but I thought it might still be of interest, plus I wanted to learn the proof. The proof is using simplicial volume(Gromov norm). You can read about this in Gromov's original paper Volume and bounded cohomology, or you can look at Thurston's notes on 3-manifolds where he discusses it. In dimension 2 a lot of the discussion can be simplified. I will basically present Gromov's proof in his Volume and bounded cohomology section $0.2$.
The idea: define a norm on chains which "records" the most efficient representation of the fundamental class(by taking infimum of chains which represent the class). Lets call this value $|| \Sigma ||$. We will prove that if you have a degree $k$ map $\Sigma \to \Sigma'$ then $||\Sigma|| \geq k ||\Sigma'||$. For a surface $\Sigma_g$, $g \geq 2$, we can show that the norm is $2|\chi (\Sigma_g)|$(basically volume!). This will give the result you want since the above shows $\chi(\Sigma_h) \geq k |\chi (\Sigma_g)|$. To prove this we will make use of some basic facts of hyperbolic geometry and that surfaces can be given a hyperbolic structure(consider right $4g$-gon in the hyperbolic plane and glue in the standard way). The intuition you should have is that the best way to "represent" the fundamental class is with an ideal triangulation of your surface. 
The norm: A real chain on $\Sigma$ is a linear combination $c=\sum_i r_i \sigma_i$, and you can define a norm $|c|= \sum |r_i|$. On homology you can define a pseudo-norm on a class $||[c]||= \inf \{ |c'| \mid c' \in [c] \}$. We define $||\Sigma||=|| [\Sigma] ||$.(This can be done for any manifold)
Lemma: $f: \Sigma \to \Sigma'$ is degree $k$ then $||\Sigma|| \geq k ||\Sigma'||$.
proof: Let $c=\sum_i r_i \sigma_i$ be a chain and $C$ is a homology class representing $C$. We have $$||f(c)||= ||\sum_i r_i f(\sigma_i)||\leq ||c||,$$ so $||f_*(C)|| \leq \inf || f(c) ||_{c \in C} \leq ||C||$(none of this depends on the degree of the map). In the case of fundamental classes we have that $f_*([\Sigma])= k[\Sigma']$, and applying the above inequality(plus obvious linearity) we get $|k| ||\Sigma'|| \leq ||\Sigma||.$
The case of surfaces: Now we want to prove that $||\Sigma_g|| = 2 |\chi(\Sigma_g)|$. First put a hyperbolic structure on $\Sigma_g$, it doesn't matter which. Note that in hyperbolic geometry geodesic triangle has area less than $\pi$ and all ideal geodesic triangles have area exactly $\pi$. Also Gauss-Bonnet tells us that such a surface has area $2\pi|\chi(\Sigma_g)|$.
Given a chain $\sum r_i\sigma_i$ representing the fundamental class. We can lift each $\sigma_i: \Delta \to \Sigma_g$ to the hyperbolic plane and straighten the triangle. We can assume that our fundamental class consists of straight simplices, and note the norm of the class can not increase. We have that $$2\pi|\chi(\Sigma_g)|=\sum r_i \int_{\Delta} \sigma_i^* dA \leq \sum |r_i|\pi$$ where the last inequality comes from the integral being less than $\pi$ since the maximal area of a straight simplex is $\pi$.
Now  divide by $\pi$ to get $$2|\chi(\Sigma_g)| \leq \inf \sum |r_i|=||\Sigma_g||.$$
Now we need $|| \Sigma_g|\ \leq 2| \chi(\Sigma_g)|=2|2-2g|$. Consider the standard $4g$-gon/$(2|\chi(\Sigma_g)|+4)$-gon that describes $\Sigma_g$. You can triangulate it with $4g-2$ triangles, and this gives a cycle representing the fundamental class. So $||\Sigma_g|| \leq 4g-2= 2|\chi(\Sigma_g)|+2$. Apply $d$-sheeted covers to the construction to get $2d|\chi(\Sigma_g)|+2$. Using our inequalites and dividing by $d$ we get $$|| \Sigma_g || \leq 2|\chi(\Sigma_g)| + 2/d.$$ Take the limit as $d$ goes to infinity to get the result.
