To complement the two answers from Daniel Shapero and Nicoguaro:
Basically, there are two ways of smoothing a mesh, subdivision (generate new vertices) and smoothing (move the points in such a way that the obtained shape is smoother).
Subdivision
To grasp the intuition, imagine you want to "smoothen" a 2D square. The 2D square is not smooth because it has corners, so let's cut the corners out, then you obtain an octagon (a "stop sign"), it has more corners, but they are wider (smoother). If you do that again, you obtain a polygon with 16 sides, that is a reasonably good approximation of a circle (do that an additional couple of times if it's not smooth enough). Now there are some theoretic results, telling you how to cut the corners in such a way that if you do that an infinite number of times, you will get a smooth (tangent continous) shape.
When can I use subdivision ?
To use subdivision, you need a mesh that is rather coarse, with well shaped elements. You need also to know that there are subdivision methods for meshes composed of quads (e.g., Catmull-Clark, Doo-Sabin) and subdivision methods for meshes composed of triangles (e.g. Butterfly, Loop, sqrt(3)). You will obtain best results with squares, but you need a very nice input mesh (e.g., a mesh designed by a computer graphics artist). If your mesh does not have a nice quad-like structure, you may try to use our "anisotropic polygonal remeshing" method cited in the other answers (disclosure: I'm a co-author of this article).
Further reading on subdivision: see Zorin et.al's SIGGRAPH course notes [1]
Smoothing
The other idea to smooth a mesh is to move the vertices in such a way that the obtained mesh is smoother. Here is some intuition about the idea: a flat mesh, where each vertex is exactly at the barycenter of its neighbors, is perfectly smooth. So one possible idea is to iteratively move all the vertices towards the center of their neighbors in interleaved loops:
(1) compute the barycenters of the neigbors
(2) move the points to the barycenter
(3) goto 1
If you do that, it works quite well, but you will observe that the mesh shrinks more and more, so you can do that with a correction phase, making the volume of the mesh constant (clearly, you need a closed mesh to do that):
(1) compute the barycenters of the neigbors
(2) move the points to the barycenter
(3) compute the volume of the mesh
(4) scale all point coordinates by the cubic root of the ratio between the new volume and the initial volume
(3) goto 1
Now, instead of correcting the volume a-posteriori, why not directly compute a volume-preserving smoothing ? This is (roughly) what Desbrun's "curvature flow" method cited in Shapero's answer does, by exploiting a relation between the curvature at a point and the volume.
Now imagine that you have some points of the mesh that need to keep their original locations, like "control nodes" that will be "locked" while all the other points are free to move. A possibility to do that, still saying that making each point as near as possible to the barycenter of its neighbors, is using least-squares: you minimize the squared distance between each point and the barycenter of its neighbors subject to the constrained points. This is called Discrete Smooth Interpolation [2],[3] (method invented by Mallet, my Ph.D. thesis advisor). It also corresponds to Laplacian smoothing (see the PMP book [4] that we wrote with colleagues, cited also in the other answers, in particular chapter 3)
So which method should I use ?
Mainly depends where the mesh comes from. Subdivision is very cheap, but only works for nice designed meshes. Curvature flow is reasonably simple, and will quite easily remove the high frequency noise from a scanned mesh. Least-squares smoothing / Laplacian smoothing needs to solve a least-squares problem (boils down to solving a linear system), which is more involved. This is the price to pay if you need to introduce constraints / control points / handles.
For the sake of completeness, I also mention spectral methods, that do a Fourier-like decomposition of the shape, see my articles and SIGGRAPH course notes on the topic [5,6], but it is extremely costly (solve eigenproblem), it's overkill in most situations (but the math. is interesting).
[1] http://mrl.nyu.edu/publications/subdiv-course2000/
[2] Discrete Smooth Interpolation, Mallet, ACM Transactions on Graphics, 1989
[3] http://alice.loria.fr/index.php/publications.html?redirect=0&Paper=smoothing@1999
[4] Polygon Mesh Processing, CRC press, Botsch, Kobbelt, Alliez, Levy, http://www.pmp-book.org/
[5] Laplacian Eigenfunctions, towards an algorithm that understands geometry, Levy, SMI 2006 invited talk
[6] Manifold Harmonics, Vallet and Levy, Eurographics / Computer Graphics Forum, 2008
[7] Spectral Geometry Processing, Levy and Zhang, SIGGRAPH and SIGGRAPH ASIA course (first given in 2010)
