Homologically trivial submanifolds Unuseful prequel
Let $M$ be a (compact, oriented, differentiable) manifold. Before knowing anything about homology theory a naif but clever mathematician may want to measure the holes in $M$ by the following procedure. One lets $B_k(M)$ be the abelian group generated by embedded submanifolds of $M$ of dimension $k$ with border. There is an obvious border operator $\delta \colon B_{k}(M) \to B_{k-1}(M)$ and trivially $\delta^2 = 0$ since the border of a manifold with border is a closed manifold. So one may define $H^K_{naif}(M)$ by taking the quotient of cycles modulo boundaries.
Ok, this does not really work, for at least two reasons. The first there is no way to make this functorial without considering more degenerate objects (singular simplices or currents being two possible choices). The second is that even if one adjusts the definition to get, for instance, the bordism groups of $M$, these will be highly nontrivial for differential geometric reasons, rather than for the topology of $M$ (for instance they will be nontrivial for a point).
Anyway, one finally chooses a working (co)homology theory, for instance singular, and then can use the fundamental class of submanifolds to link this theory to the naif one. Two questions naturally arise:


*

*Are fundamental classes of manifolds enough to generate the cohomology? This is nicely answered here.

*Are submanifolds with border enough to generate homology relations? This is the purpose of the present question.


The actual question
Let $M$ be a (compact, oriented, differentiable) manifold and let $N \subset M$ be a (closed) submanifold. The problem is to test whether $N$ is the boundary of submanifold with boundary of $M$. There are two obvious obstructions:


*

*$N$ should be bordant as an abstract variety

*The class $[N] \in H_{*}(M, \mathbb{Z})$ should be $0$.



Assume 1 and 2 hold. Are there any conditions on $M$, $N$ or the embedding $N \to M$ which guarantee that $N$ is the boundary of submanifold with boundary of $M$?

There are a few classical cases which come to mind:


*

*If $N$ and $M$ are spheres, 1 and 2 are vacuous and the thesis is true by the (generalized) Jordan curve theorem.

*If $N = S^1$ and $M = \mathbb{R}^3$, the thesis is still true by the existence of Seifert surfaces.

*If $\dim N = 1$ and $\dim M = 2$ the result seems true to me by the classification of surfaces as quotients of polygons and the usual Jordan curve theorem (but I did not check the details).


On the other hand I'm sure there are plenty of negative example even in $3$-dimensional topology. Is there anything nontrivial which can be said about this question, whether on the positive or negative side?
 A: This was supposed to be a comment to Jeff's answer, but wouldn't fit.
If you can solve the bordism problem you get a smooth map $F: W \to M$, but $F$ is not homotopic to an immersion in general. The obstruction to being one is given by the Hirsch-Smale classification of immersions, which reduces it to a problem in homotopy theory: $F$ is homotopic to an immersion if and only if $F : W \to M$ admits an "injective formal differential" that restricts to the actual differential on $\partial W$.
If it is representable by an immersion, then it can be represented by a self-transverse immersion, and if $dim(M)-dim(W) > 2$ then I think a sort of Whitney trick can be used to remove double points.
Thus I think $N \subset M$ bounds a submanifold on $M$ if an only if it bounds an abstract manifold which can be immersed into $M$.
A: A more sensitive requirement is that the map $f: N \to M$ is null bordant in the oriented bordism of $M$.  I.e., there is a manifold $W$ with boundary equal to $N$ and a map $F: W \to M$ extending the given map $f$ on $N$.  This would imply your conditions 1 and 2.   If $F$ is homotopic to an immersion (see Oscar's answer) then the question is now whether it can be made into an embedding, and I believe there is some surgery theory machinery designed to answer this question.
A: This is true in codimension and dimension 1. In fact, in these dimensions, any 
homology class is represented by an embedded manifold. In codimension 1, the
manifold $N$ will separate $M$ into (at least) two pieces. Since $N$ and
$M$ are oriented, there will be one piece which induces the orientation on
$N$, and one which doesn't. Choosing either one gives a manifold bounding $N$.
In the 1-dimensional case, one may find a map of a surface bounding the collection
of embedded closed curves. Then one can resolve the singularities to get an
embedded surface. In dimensions $5$ or higher, this amounts to transversality.
In dimension $4$, one makes the immersed surface intersect itself transversally
at finitely many points, and replace neighborhoods of these transverse intersections
with little embedded handles (annuli) to 
get an embedded surface. In dimension 3, this is a bit too complicated (although
it was carried out by Dehn). It's easier to remove a neighborhood of the link $N$
in the 3-manifold, and obtain a manifold $X = M- \mathcal{N}(N)$ with torus boundary components. 
There is a 2-dimensional homology class $x \in H_2(X, \partial X)$ which 
bounds $N$, in the sense that its boundary is a cycle in $\partial X$ meeting
each meridian of $\partial X$ algebraically once. The cycle $x$ is Poincare dual to 
$x^*\in H^1(X)$. This may be represented by a map $X \to S^1$ (by "Brown
representability", although this is much more elementary). Make this
map transverse, then the preimage of a point is a surface representing $X$ with
boundary parallel to $N$ (I think this argument
may be due to Stallings). This argument works in general to show that codimension
one homology classes are represented by manifolds. 
I don't know what the status of your question is in higher dimensions, but I
think you should look at the papers of Thom. 
A: (A similar question has since been asked here.)
This is a supplement to the answers of Jeff and Oscar, who note that first you must ask if the embedding $f\colon M \to N$ is the boundary of a smooth map $F\colon W\to N$, then ask if $F$ can be made an embedding. The bordism problem can be attacked using characteristic numbers of the map $f$. This is described in section 17 of the book "Differentiable Periodic Maps" by Conner and Floyd. In particular, their Theorem 17.5 states that

If the torsion of $H_*(N;\mathbb{Z})$ consists only of elements of order two, then maps $f_i\colon M_i\to N$, $i=1,2$ of oriented closed manifolds represent the same oriented bordism class if and only if all their Stiefel-Whitney and Pontrjagin numbers agree.

So, under these homological hypotheses, a necessary and sufficient condition for $f\colon M\to N$ to be null-bordant is that all the numbers $\langle w_I\cup f^*(x),[M]_2\rangle$ and $\langle p_J\cup f^*(x),[M]\rangle$ are zero, where $x$ ranges over the cohomology of $N$ with appropriate coefficients, and the $w_I$ and $p_J$ are monomials in the Stiefel-Whitney and Pontrjagin classes of $M$.
A: Seifert surfaces exist for oriented nullhomologous codimension two submanifolds $N\subset M$. The idea is that the linking number $lk(-,N):H_1(M-nbd(N))\to Z$ defines a cohomology class
in $H^1(M-nbd(N))$ and hence a map $f: M-nbd(N)\to S^1$. One has to adjust this map to be the projection to $S^1$ on the boundary $N\times S^1$ of the tubular neighborhood, then pull back a regular value.
