Smooth in this case just makes the surface normals at vertices point the same way, when interpolated it looks smooth. Meshsmooth would add vertices.
1) how is the smoothing possible without increasing the detailing of the mesh geometry?
Human eyes cant actually see curvature except on the edges of objects. All they can do is approximate the smoothness and process the gradient slope. So having a continuous field does give a air of smoothness. The eye however is extremely sensitive to abrupt changes in color, and interprets that as a hard crease.
By interpolating the vertex normals your surface will get the appearance of smooth flowing. Since this normal is used to calculate the final reflected color you get a smooth color field.

Image 1: a flat shaded normal versus the normals of a smooth interplation. The black normal's lie on a vertex. The colored ones are interpolated.
There is nothing that says we need to do a linear interpolation. In fact by perturbing the normals we can cause the flat surface to change appearance. This is how bump mapping and normal mapping works. The effect can be convincing unless the surfaces edge plays a too big part in which place the illusion breaks.

Image 2: a flat shaded surface (back), Smooth shaded (middle) and a mapped smooth normal. The illusion of a wavy surface breaks because the edge plays so prominent part in the image, you could instead increase the normals
2) does the smoothing at least increase the memory allocated
Hard to say definitive things about the underlying graphics engine. The normals need to be emitted to the graphics card anyway, most likely this data is cached, but could be calculated on the fly (in both cases).
Since Max uses smoothing groups it seems to me that memory usage is constant regardless. Hard to say, even if its not cached then it wouldn't make a big difference. It makes the shader tiny a bit more complicated, but only just most likely this complexity is present use it or not.