A relatively clean and intuitive proof is given in Kosinski's "Differential Manifolds," which works in the topological setting and essentially boils down to the following:
If $M$ is path-connected and $i_1,i_2:D\rightarrow M$ are isotopic embeddings (smooth or topological), then by the so-called "Cerf-Palais disk theorem" (a consequence of the Isotopy Extension Property) there is an ambient isotopy $\Phi:M\times I\rightarrow M$ (smooth or topological) such that for all $t$, $\Phi_t$ is identity outside a contractible compact set, and $\Phi(i_1(x),1)=i_2(x)$. Intuitiely, $\Phi$ translates the image of $i_1$ to the image of $i_2$, and tries hard to not effect anything else.
So if $M, i_1, i_2$ are as above, $N$ is another topological (or smooth) manifold and $i:D\rightarrow N$ is another embedding, then let $M\\#_1N$ be formed by attaching $N\setminus i(0)$ to $M\setminus i_1(0)$, and form $M\\#_2N$ using $M\setminus i_2(0)$. Since these objects are actually pushouts, we can define a homeo(diffeo)morphism in pieces: If $y\in N\setminus i(0)$, send $y$ to itself; if $y\in M\setminus i_1(0)$, send $y$ to $\Phi(y,1)$. These will assemble to give the required equivalence from $M\\#_1N$ to $M\\#_2N$. (then you could repeat the argument on the $N$ side, or just say it follows from commutativity)
The fact that the connected sum is associative and commutative follows naturally from the fact that it is actually a pushout (if you're careful, it does make a pushout in the smooth category). Then to show that it doesn't depend on the attaching disk, I think you need something equivalent to the "Cerf-Palais" theorem I mentioned.
Edit: because of what was mentioned in the comments above, it was necessary for me to assume that the embeddings were isotopic to begin with