The answer is negative. Suppose for contradiction that $S$ is such a surface, and let me first assume that it is smooth and projective.
Fix $g\geq 24$. Then the coarse moduli space of genus $g$ curves $M_g$ is of general type (this is due to Harris, Mumford and Eisenbud, see for instance [The Kodaira dimension of the moduli space of curves of genus $\geq 23$]), hence a fortiori not uniruled.
Let $H$ be the Hilbert scheme of smooth curves of genus $g$ in $S$ and let $(H_i)_{i\in I}$ be its irreducible components: the index set $I$ is countable. By hypothesis, the classifying morphism $H\to M_g$ is surjective at the level of $\mathbb{C}$-points. By a Baire category argument, there exists $i\in I$ such that $H_i\to M_g$ is dominant.
Suppose that the natural morphism $H_i\to \operatorname{Pic}(S)$ is constant. Then $H_i$ is an open subset of a linear system on $S$, hence is covered by (open subsets of) rational curves. By our choice of $g$, $H_i\to M_g$ cannot be dominant, which is a contradiction. Thus, $H_i\to \operatorname{Pic}(S)$ cannot be constant, which proves that $\operatorname{Pic}^0(S)$ cannot be trivial. Equivalently, the Albanese variety $A$ of $S$ is not trivial.
Consider the Albanese morphism $a:S\to A$. The curves embedded in $S$ are either contracted by $a$ or have a non-trivial morphism to $A$. Those that are contracted by $a$ form a bounded family, hence have bounded genus. Curves $C$ that have a non-trivial morphism to $A$ are such that there is a non-trivial morphism $\operatorname{Jac}(C)\to A$, but this is impossible if $\operatorname{Jac}(C)$ is simple of dimension $>\dim(A)$. Consequently, a smooth curve with simple jacobian that has high enough genus cannot be embedded in $S$. This concludes because a very general curve of genus $g$ has simple jacobian (there even exist hyperelliptic such curves by [Zarhin, Hyperelliptic jacobians without complex multiplication]).
As pointed out in the comments, the argument needs to be modified if $S$ is non-algebraic or singular. I explain now these additional arguments.
If $S$ is smooth but non-algebraic, we can use the following (probably overkill) variant. We can consider the open space $H$ of the Douady space of $S$ parametrizing smooth connected curves in $S$. It is a countable union of quasiprojective varieties by [Fujiki, Countability of the Douady space of a complex space] and [Fujiki, Projectivity of the space of divisors on a normal compact complex space]. It has an analytic morphism to the analytic space $\operatorname{Pic}(S)$ parametrizing line bundles on $S$ [Grothendieck, Techniques de construction en géométrie analytique IX §3]. The dimension of $\operatorname{Pic}(S)$ is finite equal to $h^1(S,\mathcal{O}_S)$. The dimension of the fibers of $H\to\operatorname{Pic}(S)$ is at most $1$. Indeed, otherwise, we would have a linear system of dimension $>1$ on $S$ consisting generically of smooth connected curves, hence a dominant rational map $S\dashrightarrow\mathbb{P}^2$, showing that $S$ is of algebraic dimension $2$, hence that $S$ is algebraic. It follows that every connected component of $H$ has dimension $\leq h^1(S,\mathcal{O}_S)+1$. Now choose $g$ such that $\dim(M_g)>h^1(S,\mathcal{O}_S)+1$, and let $H_g$ be the union of connected components of $H$ parametrizing genus $g$ curves. A Baire category argument applied to the image of $H_g\to M_g$ shows that there are genus $g$ curves that do not embed in $S$, as wanted.
Finally, if $S$ is singular, consider a desingularization $\tilde{S}\to S$. The hypothesis on S implies that every smooth projective curve may be embedded in $\tilde{S}$, with the exception of at most a finite number of isomorphism classes of curves (namely, the curves that are connected components of the locus over which $\tilde{S}\to S$ is not an isomorphism). The arguments above apply as well in this situation.
You can take $y_0 = 0$, $y_1 = -tx_1^m$, $y_2 = x_0^m$.
EDIT. Here is a simple computation of the normal bundle of the curve
$$
C_t = \{([x_0:x_1],[0:-tx_1^m:x_0^m])\} \subset \mathbb{P}^1 \times \mathbb{P}^2
$$
in the surface
$$
S_t = \{x_0^ny_1−x_1^ny_0+tx_0^{n−m}x_1^my_2=0\}
$$
for $t \ne 0$. First, the normal bundle fits into the exact sequence
$$
0 \to N_{C_t/S_t} \to N_{C_t/\mathbb{P}^1 \times \mathbb{P}^2} \to N_{S_t/\mathbb{P}^1 \times \mathbb{P}^2}\vert_{C_t} \to 0.
$$
Since $C_t$ is a graph of a map $\mathbb{P}^1 \to \mathbb{P}^2$ (of degree $m$), its normal bundle is the pullback of the tangent bundle of $\mathbb{P}^2$, hence its degree is
$$
\deg(N_{C_t/\mathbb{P}^1 \times \mathbb{P}^2}) = 3m.
$$
On the other hand, $S_t$ is a divisor of type $(n,1)$ on $\mathbb{P}^1 \times \mathbb{P}^2$, hence its normal bundle restricted to $C_t$ has the degree
equation which has degree
$$
\deg(N_{S_t/\mathbb{P}^1 \times \mathbb{P}^2}\vert_{C_t}) = n + m.
$$
Therefore,
$$
\deg(N_{C_t/S_t}) = 3m - (n + m) = 2m - n.
$$
Best Answer
The first thing I would like to point out is that the variety we care about is actually
{$([x_0 , x_1 ],[y_0,y_1,y_2]):{x_0}^n y_1 - {x_1}^n y_2 =0$}$ =V \subset \mathbb{P}^1 \times \mathbb{P}^2$
(the defining equations you gave are not usually homogenous, and this is what Huybrechts gives in his book: http://books.google.com/books?id=eZPCfJlHkXMC&q=hirzebruch).
We want to start out by thinking about $\mathbb{P}^1 \times \mathbb{P}^2$ as a $\mathbb{P}^2$ bundle over $\mathbb{P}^1$. In particular, it comes with the distinguished line bundle $\pi_2^*\mathscr{O}_{\mathbb{P}^2}(1)$ ($\pi_2$ is the projection onto $\mathbb{P}^2$). Now we examine the short exact sequence of sheaves of modules which defines V:
$0\rightarrow \pi_1^*\mathscr{O}_{\mathbb{P}^1}(-n) \otimes \pi_2^*\mathscr{O}_{\mathbb{P}^2}(-1)\rightarrow \mathscr{O} _{\mathbb{P}^2\times\mathbb{P}^1} \rightarrow \mathscr{O}_V\rightarrow0$.
We would like to apply ${\pi_1}_*$ on this sequence after twisting by $\pi_2^*\mathscr{O}_{\mathbb{P}^2}(1)$. The point of this is that if you believe that $V$ is a $\mathbb{P}^1$ bundle over $\mathbb{P}^1$ (which you should because you can check it on charts) then ${\pi_1}_*(\mathscr{O}_V \otimes \pi_2^*\mathscr{O}_{\mathbb{P}^2}(1))$ should be the corresponding locally free sheaf of rank 2. So we can then check to see if it is isomorphic to $\mathscr{O} _{\mathbb{P}^1}\oplus\mathscr{O} _{\mathbb{P}^1}(n)$.
After twisting and applying ${\pi_1}_*$, we get the sequence:
$0\rightarrow \mathscr{O}_{\mathbb{P}^1}(-n)\rightarrow \mathscr{O} _{\mathbb{P}^1}^{\oplus 3} \rightarrow {\pi_1}_*(\mathscr{O}_V \otimes \pi_2^*\mathscr{O}_{\mathbb{P}^2}(1))\rightarrow0$.
(In general one does not get exactness on the right, but in a situation like this we do)
And by figuring out what our maps are doing we should be able to argue that the sheaf on the right is some line bundle twist of $\mathscr{O}_ {\mathbb{P}^1}\oplus \mathscr{O}_{\mathbb{P}^1} (n)$, which implies $V \cong \mathbb{P}(\mathscr{O} _{\mathbb{P}^1}\oplus\mathscr{O} _{\mathbb{P}^1}(n))$.