Riemannian 2-manifolds not realized by surfaces in $\mathbb{R}^3$?
The hyperbolic plane cannot be smoothly isometrically embedded in $\mathbb{R}^3$. It can be so in $\mathbb{R}^5$. It is open (as far as I know) if it can be embedded in $\mathbb{R}^4$. I believe this is mentioned in Do Carmo's book on curves and surfaces.
Edit: Not a complete characterization, but Amsler has shown (see below for reference) that any Riemannian surface with constant negative curvature, if attempted to be imbedded in $\mathbb{R}^3$, must have singularities.
Amsler, M.H., Des surfaces a courbure negative constante dans l'espace a trois dimensions et de leurs singularites, Math. Ann. 130, 1955, 234-256
The Whitney embedding theorem says you can always embed a smooth $n$-manifold in $\mathbb{R}^{2n}$, and immerse it in $\mathbb{R}^{2n-1}$. Nonorientable Riemann surfaces, for example, don't embed in $\mathbb{R}^3$, but there are some pretty good immersions (the typical picture of the Klein bottle is a good example).
For a Riemannian manifold, Nash and Kuiper proved that there's a $C^1$ globally isometric embedding into $\mathbb{R}^{2n+1}$ (and, in fact, that you can arbitrarily closely approximate any metric $C^\infty$ embedding into at least $\mathbb{R}^{n+1}$ by a global isometric $C^1$ embedding). For a global isometric $C^\infty$ embedding, it looks like the current lower bound is max$(n(n+1)/2+2n,n(n+1)/2+n+5)$. For a local one, you can do it into $n(n+1)/2+n$-space.
This means that for a globally isometric and analytic embedding of a surface, you might have to go up to $\mathbb{R}^{10}$. Ew.
There are pointers to a wealth of information on this question in the responses to the Math Overflow question, which you mentioned in your comment to Paul VanKoughnett's response.
In particular, Deane Yang's response gives a nice summary of the situation, and Bill Thurston's response seems to give a good perspective on the problem of trying to find a characterization of Riemannian manifolds that admit such an embedding.
Regarding the third question you mention in an edit. This is essentially a local problem. All this from the same MO question:
From BS's response: there is not even a local isometric embedding in general: http://www.springerlink.com/content/m775p64w64351260/
from Will Jaggy's response (and Deane Yang's comments on it): If the metric is analytic, then you can construct a local isometric embedding. Some recent progress on characterizing the requirements when the degree of smoothness is relaxed: http://arxiv.org/abs/1009.6214 The bibliography for that last one has no shortage of other relevant sounding titles.