This basic question is unfortunely not well explained anywhere in the literature that I know of, although the answer is well known to lots of people. When $\pi_1(S)$ embeds into $\pi_1(M)$ and $\pi_1(N)$, then the answer can be expressed in terms of *graphs of groups*, explained in Serre's book *Trees*. Without the $\pi_1$-injectivity assumption, the answer is no longer a graph of groups, but the presentations that Serre gives you still work. Since you are motivated by topology, you might also be interested in Scott and Wall's article *Topological methods in group theory*.


In any case, I will try to sketch the answer, with an emphasis on giving actual presentations that you can use.

I will assume that $S$ is 2-sided, so the boundary of the normal bundle of $S$ consists of two copies of $S$; let's denote them $S_+$ and $S_-$. Let $M_0$ be the result of cutting $M$ along $S$ and $N_0$ the result of cutting $N$ along $S$. The generalised connect sum is now the glued manifold

$M\#_S N=M_0\cup_{S_+\cup S_-} N_0$.

I will also assume that $S$ is connected; if not, you can deduce the final answer by iterating the calculation below. Finally, let's use $i:S_+\cup S_-\to M_0$ and $j:S_+\cup S_-\to N_0$ for the inclusion maps.

There are several cases depending on whether or not $M_0$ and $N_0$ are connected. If $M_0$ is disconnected, write $M_0=M_+\sqcup M_-$, where $S_\pm\subseteq M_\pm$, and similarly for $N_0$.

If $M_0$ and $N_0$ are both disconnected, then the glued manifold is also disconnected, and so you need to compute the fundamental groups of the components separately, which can be done using the Seifert--van Kampen theorem. You get:

$\pi_1(M_\pm\cup_{S_\pm}N_\pm)\cong \pi_1(M_\pm)*\pi_1(N_\pm)/\langle\langle i(g)^{-1}j(g)\mid g\in\pi_1(S_\pm)\rangle\rangle$.

When the inclusion maps are injective on $\pi_1$, this is the amalgamated free product

$\pi_1(M_\pm)*_{\pi_1(S_\pm)}\pi_1(N_\pm)$.

If $M_0$ is connected but $N_0$ is disconnected, then

$M\#_S N= N_+\cup_{S_+} M_0\cup_{S_-}N_-$

and the fundamental group can be computed by iterating the calculation from the previous case. In particular, if the inclusion maps are $\pi_1$-injective then you get the result

$\pi_1(M\#_S N)=\pi_1(N_+)*_{\pi_1(S_+)} \pi_1(M_0)*_{\pi_1(S_-)}\pi_1(N_-)$.

Finally, the most interesting case is when both $M_0$ and $N_0$ are connected. Many people will start to talk about groupoids at this point, but this is an unnecessary complication. You should read about *HNN extensions* in the sources I mentioned above. In any case, the answer is

$\pi_1(M\#_S N)=\pi_1(M_0)*\pi_1(N_0)*\langle t\rangle/\langle\langle\{ i(g_+)^{-1}j(g_+)\mid g_+\in\pi_1(S_+)\},\{ i(g_-)^{-1}tj(g_i)t^{-1}\mid g_-\in\pi_1(S_-)\}\rangle\rangle$.

Note the conjugation by $t$. Topologically, $t$ represents a loop that starts in $M_0$ (say), traverses $S_+$ to enter $N_0$ and exits $N_0$ through $S_-$.

When the inclusion maps are $\pi_1$-injective, this decomposes $\pi_1(M\#_S N)$ as a graph of groups, with underlying graph a circle. 

Note that, in all cases, the answer isn't just a function of $\pi_1(M)$ and $\pi_1(N)$; you also need to understand the complementary manifolds $M_0$ and $N_0$, and how the surface $S$ sits inside them.