I'm looking for an elegant proof that any closed, oriented $3$manifold $M$ is the boundary of some oriented $4$manifold $B$.

I know of several different arguments. You can decide which one you think is most elegant...
The reason to prefer our proof (number 4) is that it is more efficient, in that (e.g.) for a 3manifold triangulated with $n$ tetrahedra, it gives a 4manifold with bounded geometry with $O(n^2)$ simplices. By comparison, the mappingclass group arguments of (3) tend to give a 4manifold of complexity at least exponential in $n$, and usually a tower of exponentials. (You can see this already in the inductive argument sketched out in Daniel Moskovich's answer.) Thom's proof (2) is completely nonexplicit; I don't know how to extract any bounds from it. Rohlin's proof (1) can, I believe, be shown to give a 4manifold with $O(n^4)$ simplices, although I never worked out all the details. 


Maybe overkill, but elegant: By a theorem of Hirsch, an oriented $3$manifold $M$ embeds in the $5$sphere (nonorientable case: Rohlin and Wall, independently). By Alexander duality, $M$ bounds a "Seifert $4$manifold." (Some references: Hirsch, Immersions of almost parallelizable manifolds. Proc. Amer. Math. Soc. 12 1961 845–846. Rohlin, The embedding of nonorientable threemanifolds into fivedimensional Euclidean space. Dokl. Akad. Nauk SSSR 160 1965 549–551. Wall, All 3manifolds imbed in 5space. Bull. Amer. Math. Soc. 71 1965 564–567. ) 


MR0809959 (87f:57016) Rourke, Colin . A new proof that $\Omega_3$ is zero. J. London Math. Soc. (2) 31 (1985), no. 2, 373376. 

