I'll expand a bit the comments by Igor Rivin and myself above.

The way I see it, there are two ways of constructing such a curve, and they both involved what I'd call "embedded connected sum". This is the construction you outlined above, and is an adaptation of the usual connected sum construction.

If you're given two $n$-dimensional manifolds $X_1, X_2$ and two embedded $m$-dimensional submanifolds $Y_1, Y_2$, you can embed $Y_1\# Y_2$ in $X_1\# X_2$ exactly as you described.

In the case at hand, the second homology of the connected sum of two 4-manifolds is the direct sum of the two homologies, and $Y_1\# Y_2$ is going to be nontrivial if and only if one of $Y_1$ and $Y_2$ is nontrivial in homology.

One way to produce the embedding you look for is then the following: take a cubic $C$ and a quartic (*i.e.* degree-4 curve) $Q$ in $\mathbb{CP}^2$. The degree-genus formula tells you that $g(C) = 1$ and $g(Q) = 3$, so you can embed $C\# Q$ in $\mathbb{CP}^2\#\mathbb{CP}^2$. The homology class of this curve is going to be $(3,4)$, as you mention, and in particular it's homologically nontrivial. I believe (but I should check) that this curve happens to be of minimal genus in its homology class.

A second way to produce the same result shows that, as I mentioned above, it's always possible to increase the genus in a given homology class (while it's very hard to determine how low you can go). The key fact is that it's easy to produce embedded surfaces in $S^4$ of arbitrary genus. In fact, one can do it in $S^3$ (for example, with Heegaard decompositions; or notice that it's enough to do it for genus 1 and then use the embedded connected sum, for example) and then embed everything in $S^4$. As a result, we can have a surface $F$ of genus 4 embedded in $S^4$. Now just take the embedded connected sum of two complex lines (topologically, just spheres) and $F$. This gives a surface of genus $4$ in $\mathbb{CP}^2\#\mathbb{CP}^2$, which is homologically nontrivial (in fact, of class $(1,1)$).

This same construction can be tweaked to realise the classes $(0,1), (0,2), (1,2), (2,2), (0,3), (1,3), (2,3), (3,3), (0,4), (1,4)$ and $(2,4)$ (and their symmetric) as well, but as soon as you hit $(5,m)$ or $(4,4)$ you should violate the adjunction inequality (see Kronheimer and Mrowka's proof of the Thom conjecture). Take all this last part with a grain of salt, though.

Finally, I'd like to add two comments for completeness.

There's an easier way to see that a degree-$d$ curve $X_d$ in $\mathbb{CP}^2$ represents the homology class $d\cdot H$ ($H$ is the hyperplane class -- I'll drop brackets throughout for convenience): since $H_2(\mathbb{CP}^2)$ is cyclic and generated by $H$, one only needs to compute $H\cdot X_d$. But this just counts the intersections of a complex line with a complex curve of degree $d$, and these are $d$, and they are all positive, so the intersection is exactly $d$. This is roughly the same way you show that the hyperplane class has square 1.

The formula you refer to, giving you the genus of a smooth curve in terms of its degree, is called the degree-genus formula. One of the way to prove it, is projecting from a point (either on the curve or outside) to a generic line and looking at the restriction of this map to the curve. This is going to be a branched cover, and an application of the Hurwitz formula gives you the result. This is really a nice exercise/theorem on Riemann surfaces.

decreasingit. – Marco Golla May 18 '14 at 18:31