Here is a more detailed answer which somehow sums up the comments and remarks above.
To begin with, what I say is valid more generally on every smooth projective manifold: you don't need to restrict your attention to surfaces! On the other hand, you must require projectivity (which you don't do in your question) otherwise what you ask is not true (think of a non-projective complex torus without complex subvarieties).

Let $X$ be complex projective manifold and $[\alpha]\in H^{1,1}(X,\mathbb Z)$ be an integral $(1,1)$-Hodge class. The Lefschetz theorem on $(1,1)$-classes says that the first Chern class map $\operatorname{Pic}(X)\to H^{1,1}(X,\mathbb Z)$ is in fact surjective.

This means that there exists on $X$ a line bundle $L\to X$ such that $c_1(L)=[\alpha]$.

Now, on a smooth projective manifold one always has $\operatorname{Pic}(X)\simeq\operatorname{Div}(X)/\sim$, where $\sim$ is linear equivalence of divisors. Thus, there exists an integral divisor $D=\sum a_j D_j$, $a_j\in\mathbb Z$ not necessarily positive, on $X$ such that the associated line bundle $\mathcal O_X(D)\simeq L$. In particular, $c_1(L)$ equals the cohomology class $[D]$ of $D$ (that is the Poincaré dual of the homology class of $D$). The integral (in general non-effective) cycle $D$ is what you are looking for.

Notice that the above isomorphism between the Picard group and the linearly equivalence classes of divisors can be rephrased saying that $L$ does always admit a (a priori) meromorphic section $s$: then set $D=\operatorname{div}(s)$.

Next, when can $[\alpha]$ be represented by an effective cycle (i.e. with all the $a_j\ge 0$)?. This is a much more subtle question.

Observe, first of all, that effectiveness is *not* in general a numerical property (i.e. it does not depend only on the first Chern class of the line bundle, or rather on how it intersects curves). To see this let $C$ be a smooth curve. Then, of course, two line bundles are numerically equivalent if and only if they have the same degree. If the genus $g$ of $C$ is greater than $1$, then the map
$$
\Phi\colon C\to\operatorname{Jac}^1(C)
$$
to the $g$-dimensional torus $\operatorname{Jac}^1(C)$ parametrizing degree $1$ line bundles on $C$ is an embedding. Its image corresponds to line bundles of the form $\mathcal O_C(p)$, for some $p\in C$, which are exactly the effective degree $1$ line bundles. Since $\dim\operatorname{Jac}^1(C)>\dim C$ by the hypothesis on the genus, you see that you can find a degree $1$ line bundle which is not effective (note also, in passing, that all line bundles of positive degree on a curve are ample, so that this example shows also that you can find non-effective ample line bundles -even if they eventually are, taking their tensor powers).

Of course, if $A\to X$ is a very ample or globally generated line bundle, then it is effective. Unfortunately, neither very ampleness nor globally generation are numerical properties (while ampleness, as well as nefness, bigness and pseudo-effectiveness are).

So, what you can do instead is to look at rational objects, that is to "tensor" the above $\mathbb Z$-modules by $\mathbb Q$. In this way, you can look at powers of a line bundle, hoping that it will become eventually effective and then "divide" by the same power to come back to the starting object.

In this way, if you know that $[\alpha]$ is big or ample (which, I repeat, depends only on $[\alpha]$), then you can conclude that it is $\mathbb Q$-effective: a high power $L^{\otimes m}$ in this case will have a global holomorphic section so that $L^{\otimes m}\simeq\mathcal O_X(D)$, with $D$ integral and effective, and thus $[\alpha]=[\frac 1m D]$ in rational cohomology.

very amplethen what you want is true, since $h^0(X, A) >0$. – Francesco Polizzi Jul 24 '12 at 12:16