If the normal bundle of $\Sigma$ in $M$ is orientable, then there always exists such a foliation. The idea is that one can construct a smooth function $f$ on $M$ such that $\Sigma$ is the set of zeros of $f$ and $\mathrm{d}f$ does not vanish on a tubular neighborhood of $\Sigma$. Then, since, by Theorem 6.2, Chapter II of Golubitsky and Guillemin's Stable Mappings and their Singularities, the Morse functions on $M$ are an open dense subset of $C^\infty(M,\mathbb{R})$, there will be a Morse function $g$ on $M$ that is sufficiently close to $f$ in the $C^\infty$ topology that the locus $g=0$ is ambiently isotopic to $\Sigma$. By composing with a diffeomorphism of $M$, we can assume that $\Sigma$ is the zero locus of $g$. Since $g$ is a Morse function, it has isolated critical points (and therefore a finite number of them). Away from the critical points the level sets of $g$ define a foliation of $M$ whose zero level set is $\Sigma$. As for the minimal number of such critical points, that will depend on the topology of the two 'sides' of $\Sigma$ in $M$.
In the non-orientable case, you can do the following. First, fix a Riemannian metric on $M$ and foliate a small tubular neighborhood of $\Sigma$ by level sets of the distance function. For any sufficiently small positive $\epsilon$, the set of points $\Sigma_\epsilon$ with distance $\epsilon$ from $\Sigma$ will be a smooth hypersurface that is a double cover of $\Sigma$, and its normal bundle will be trivial. We can apply the above argument to the part of $M$ that lies outside of the (open) $\epsilon$-tube about $\Sigma$ to foliate it by smooth hypersurfaces outside of a finite number of critical points of some appropriate Morse function. Again, bounding the number of isolated singularities will depend on the topology of $M$ and $\Sigma$.