This basic question is unfortunately 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.