To find higher genus curves without using a specific embedding $S \subset \mathbb{P}^n$, it could help to think first about the case when your surface is actually a product $S=\mathbb{P}^1 \times E$. Let $C$ be a curve which admits two branched covers, $f\colon C \to E$ and $g \colon C \to \mathbb{P}^1$. Then the product $f \times g \colon C \to S$ maps into the surface $S$. If the branch points of $f$ and $g$ are different then $f \times g$ will even be an embedding.
In general, let $V \to E$ be your rank-two vector bundle, so $S=\mathbb{P}(V)$. Given a banched cover $f \colon C \to E$, you pull back $V$ to a bundle $V' \to C$. Now every time you have a line sub-bundle $L$ of $V'\to C$ you get a section of $\mathbb{P}(V')$ which plays the role of $g$ in the first paragraph. It can be combined with $f \colon C \to E$ to give a map $C \to S$. When looking for line sub-bundles, don't forget that you can tensor your original bundle $V$ by any line bundle over $E$ without changing $\mathbb{P}(V)$. Depending on how much you know about $E$ and $V$, hopefully this should help you find plenty of explicit curves in $S$.
