A simple closed curve $\gamma$ in an orientable genus $g$ surface $M$ is nullhomologous if and only if $M \setminus \gamma$ consists of two connected components, one of which is a surface $N$ with $\partial N = \gamma$.
Could anybody prove this or show a book where it's clearly explained?
What you are asking for is a special case of "Poincare duality", see also this question. Guillemin and Pollack is my favorite reference.
Suppose you have a nonseparating simple loop $a$ in $S$. Since $a$ is nonseparating, there exists a simple loop $b$ in $S$ which crosses $a$ transversally in exactly one point. Orienting these loops, we can assume that this intersection is positive. Oriented loops in $S$ define cycles and, hence, elements of $H_1(S;Z)$; since the oriented intersection number $I(a,b)$ is independent of the representative of the homology class, it follows that such $a$ is homologically nontrivial.
Conversely, suppose that $a$ separates. Then for every simple loop $b$ in $S$ transversal to $a$, the oriented intersection number $I(a,b)$ is zero (all intersection points come in pairs with opposite signs). Therefore, $a$ is null-homologous. You can also see this directly, without appealing to Poincare duality: Let $M\subset S$ be a subsurface with boundary bounded by $a$. Triangulate $M$ and orient 2-simplices consistently. The sum of these oriented simplices is a 2-chain whose boundary is $a$, regarded as a triangulated 1-cycle.
The same argument works in all dimensions, when you use closed (triangulated) hypersurfaces in a triangulated manifold. (This can be also done topologically or in the smooth category.)