The Nash embedding theorem tells us that every smooth Riemannian mmanifold can be embedded in $R^n$ for, say, $n = m^2 + 5m + 3$. What can we say in the special case of 2manifolds? For example, can we always embed a 2manifold in $R^3$?

The NashKuiper embedding theorem states that any orientable 2manifold is isometrically ${\cal C}^1$embeddable in $\mathbb{R}^3$. A theorem of Thompkins [cited below] implies that as soon as one moves to ${\cal C}^2$, even compact flat $n$manifolds cannot be isometrically ${\cal C}^2$immersed in $\mathbb{R}^{2n1}$. So the answer to your question for smooth embeddings is: No, as others have pointed out. I believe Gromov reduced the dimension you quote of the space needed for any compact surface to 5, but I don't have a precise reference for that. Tompkins, C. "Isometric embedding of flat manifolds in Euclidean space," Duke Math.J. 5(1): 1939, 5861. Edit. Both Deane Yang and Willie Wong were correct that the Gromov result is in Partial Differential Relations. I believe this is it, on p.298: "We construct here an isometric $\cal{C}^\infty$ ($\cal{C}^{\mathrm{an}}$)imbedding of $(V,g) \rightarrow \mathbb{R}^5$ for all compact surfaces $V$." $g$ is a Riemannian metric on $V$. 


Lately I've been designing and making collections of pieces, cut from foam with a computercontrolled 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 nonnegatively 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 nonC^2 embedding of the NashKuiper 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 uptodate 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 nontrivial way. 


I'd like to summarize and elaborate on what's been said: First, closed nonorientable surfaces such as the Klein bottle have no topological embedding in $R^3$ and therefore no isometric embedding. The question is more reasonable if restricted to, say, closed orientable surfaces. Without the topological obstruction, this is a question about global solutions to the system of PDE's given by the isometry condition. But not any global solution. A global solution is necessarily an immersion but not necessarily an embedding. Moreover, the system of PDE's is a rather nasty one. It can be rewritten as a single MongeAmpere equation, whose type is determined by the sign of the Gauss curvature, so the equation is elliptic where the Gauss curvature is positive and hyperbolic where the curvature is negative. Near a point where the Gauss curvature changes sign but has nonzero gradient, the equation is called "Tricomi type". As pointed out by José, there is a geometric obstruction to global solutions: any isometrically embedded surface has at least two points with positive Gauss curvature (given by the two points of contact of an osculating sphere). So, for example, orientable surfaces with nonpositive curvature have no isometric embedding in $R^3$. At this point, if you're still focused on isometric embeddings in $R^3$, then the question is whether any oriented surface with "enough" positive Gauss curvature is isometrically embeddable. The only result I know in this direction is Nirenberg's solution to the Weyl problem, which states that any closed surface with positive Gauss curvature has a unique isometric embedding in $R^3$. This and Nirenberg's solution to the 2d Minkowski problem launched a golden era of using nonlinear elliptic PDE theory to solve many hard global problems in differential geometry, as exemplified by the work of Yau and Schoen. Or you could go to higher dimensions. By now I don't remember the details, but I think that it is correct that Gromov showed that any 2d surface can be isometrically embedded in $R^5$. I also don't remember where the proof is given, but the first place to look is his book, Partial Differential Relations, where he shows how to solve systems of underdetermined PDE's using "soft" techniques such as the hprinciple. The ideas in this book sit somewhere between the hard analysis of PDE theory (he actually provides a proof of the NashMoser implicit function theorem) and the soft or "flabby" approach of topology. Either the proof or a reference to it should be in the book somewhere. 


I'm not convinced this is an appropriate question, but giving the benefit of the doubt and since the OP is probably not a geometer... The flat torus cannot be smoothly embedded in $\mathbb{R}^3$ isometrically. Since the torus is compact, any embedded torus lies in the interior of some sphere centered at the origin. Decrease the radius of the sphere until it just touches the torus for the first time. At the point of contact, the curvature of the torus agrees with that of the sphere, and is hence positive. 


There are interesting material on embedding surfaces in $R^3$ in the book Isometric Embedding of Riemannian Manifolds in Euclidean Spaces by Qing Han and JiaXing Hong, AMS, 2006. See this link. Moreover, it seems that even embedding a small neighborhood of a point can be problematic, but I don't know if there is a smooth counterexample. 


I had a conversation today with Christopher Croke of Penn., he pointed out that there was progress, extremely recent progress, on the local version, isometrically embedding a piece of surface in $\mathbf R^3.$ This is all in the $C^\infty$ category, it is always possible that more is known in $C^\omega$ and very likely less is known in, say $C^2.$ Anyway, if the curvature does not vanish in the neighborhood, then it can be isometrically embedded in $\mathbf R^3.$ The same is true if the curvature vanishes at a point but some directional derivative does not. Well, from a new item on the arXiv by Qing Han and Marcus Khuri,
The title of the preprint is "On the Local Isometric Embedding in $\mathbf R^3$ of Surfaces with Gaussian Curvature of Mixed Sign." http://arxiv.org/abs/1009.6214 Both Han and Khuri have published on this topic in the Journal of Differential Geometry, Han in 2003, Khuri in 2007. 


Another counter example, and somehow more exotic, is the Klein bottle. 

