Lately I've been designing and making collections of pieces, cut from foam with a computer-controlled cutter, that can be joined to one another in an interlocking way to approximate an arbitrary surface, so I've become more aware of some of the obstructions to smooth isometric embeddings. (A few of some earlier versions of the modelling sytem are shown on the home page of Kelly Delp, with whom I've been collaborating). Here are two examples:
It seems like an interesting question to give good sufficient conditions beyond the non-negatively curved case and good obstructing conditions, beyond conditions that I will outline below. (I'm not an expert in this stuff, so there may be much more that is known.)
In the first place, any smooth closed surface M^2 in R^3, if you think about the Gauss map (the point of the unit normal vector, translated to be based at the origin), it is clear that the closure of the subset of M^2 that has positive Gaussian curvature map surjectively --- it suffices to take the point on the surface that maximizes inner product with a vector in that direction. In other words, there must be at least 4 pi worth of positive curvature. (For the construction kits, this gives a linear inequality for how many seams of various types are needed to construct a closed surface in space).
The above condition is not sufficient. If you start from a standard torus obtained as a circle of revolution, the Gauss map covers the sphere precisely twice, once with positive orientation from the outer shell, and once in the negative sense from the inner part. The positively curved part meets the negatively curved part on two round circles, along which the normal vectors are parallel and so the Gauss map is constant. For any slight perturbation of this surface in space, the Gauss map changes, but the area of the two regions is constant up to first order: the area of the image changes by the area swept out by the evolving boundary curve, but the Gauss image boundary curves of length zero have to grow before they can begin to capture area.
It's easy to perturb the metric of a round torus to make the total positive part of Gaussian curvature increase to first order. These perturbations of the metric can't be extended to perturbations of the embedding. If you do this perturbation on a portion of the torus, half a bagel so to speak, it increases its angle of curling.
I don't at the moment know a rigorous proof that there are no smooth embeddings of these perturbed metrics, but I suspect a proof could be given. (If one had a sequence of eapproximating metrics, one technical issue is that they might admit embeddings having greater and greater variation of the 2nd derivative, so the limit might be a non-C^2 embedding of the Nash-Kuiper embeddings as described by Deane Yang.)
In practice, constructions made from pieces of foam that approximate a torus of revolution are surprisingly rigid --- there is very little tolerance to modify the embedding in a way that will make it close if it doesn't want to.
On the other hand, if you change the torus shape to add a corkscrew effect, the Guass map on the boundary betwen positive and negative is no longer constant. These shapes have much greater ability to accomodate a change in the metric.
It's easy to come up with many other examples of surfaces where there are components of the positively curved part bounded by curves that have parallel normal vectors --- people often draw these instinctively. These surfaces are all limited by the same kind of rigidity.
There is another class of obstructions I'm aware of that from Hilbert's theorem that for any hyperbolic surface with a real analytic isometric immersion in space, the total |Gaussian curvature enclosed| by a quadrilateral of asymptotic lines is less than 2 pi (the upper bound for areas of quadrilaterals in the hyperbolic plane). This has subsequently been generalized in several ways, but I'm not up-to-date on what's known. The trouble is that one doesn't easily know ahead of time what the asymptotic lines will be. However, this gives some qualitative obstrutions, so I suspect one could prove that if you take two copies of a large disk in the hyperbolic plane and bridge between them by an annulus of positive curvature, the resulting metric on the sphere has no C^2 isometric embedding. If you make paper models, in practice they get riffly edges that are qualitatively incompatible with a C^2 isometric approximation, because the asymptotic line fields turn in a homotopically non-trivial way.