In generating an elevation profile, samples from the underlying raster must be taken. If the objective is to create a profile of maximum quality, how should the locations of sample points be determined? What approach should be taken to interpolating those sample points?
If you want create a profile of maximum quality, then your algorithm has to basically include every single cell that is intersected by your query path and then it becomes a simple 2D curve fitting problem. However, if you want to just sample a subset of those points and create a profile that is more visually pleasing, you may that find that this paper from geocomputation has a lot of different interpolation technique for sampling elevation as well as the math behind it.
An elevation profile computes the intersection of two surfaces. One of them is a vertical sheet determined by a path. (That is, it consists of all coordinates (x,y,z) where (x,y) is on the path and z is any number.) The other is the surface represented by the raster DEM. As such, it amounts to finding the z-values lying above points on the curve. This makes it identical to the problem of interpolating values from the raster. In particular, although it shares many characteristics of the simpler one-dimensional problem of fitting a curve to (distance, elevation), data, it is not the same situation. Viewing it as such is likely to produce sub-optimal elevation profiles because you will not have taken advantage of the information in the full 2D extent of the raster data on either side of the curve.
Evidently, all the considerations that attach to interpolating surfaces are relevant here. There are many competing methods, each with advantages and disadvantages, each appropriate for varying uses, and each with its own "quality." They include (but are not limited to):
These are all algorithms to estimate a value z(x,y) from the data, given an arbitrary location (x,y) which is not necessarily coincident with any data point. This is how a raster dataset is drawn, by the way: to determine the color at a particular pixel (u,v) on the screen or paper (the map), the world coordinates (x,y) of the pixel are computed, the value z(x,y) is calculated using the interpolator, and that value is converted to a color using a ramp or a lookup table. (For efficiency, I suspect many GISes do not perform this procedure at every pixel: instead, they take a regular subsample of the pixels, figure out their colors, and then perform some simple interpolation of the color across the screen or paper.)
We can think of the pixels as determining a regular sample of planar locations for interpolation. Creating an elevation profile involves a similar consideration: where to locate the "pixels" along the path? The answer is developed in the same way we would answer the corresponding question for map making: what scale do you need? At large scales (zoomed way in) you need much closer sampling; at small scales you can sample with a larger spacing. If you're clever, you can even use adaptive or recursive methods to focus the sampling on where the z-values are varying the most rapidly, have the greatest curvature, or are attaining extreme values. If you're not as clever, or don't need the best representation, you can create a set of equally-spaced values along the path at distances d(0) < d(1) < ... < d(n) along the path and, from the nearby raster values, interpolate corresponding elevations z(0), z(1), ..., z(n). You would then plot the pairs (d(0), z(0)), ..., (d(n), z(n)) and fair in some kind of curve around them--usually a spline--assuming that the variations z(i+1) - z(i) are sufficiently small that how the curve is fit doesn't matter. (The adaptive methods inspect these variations and obtain more interpolated values at intermediate distances where it appears there is large variation.)
This gets us to the heart of the question: what should the initial sample distances be? The answer depends on the intended scale of the elevation profile, the accuracy of the DEM's values, the accuracy with which the curve is registered to the DEM locations, and the rate of variation of elevations along and near the profile. In general, larger scales (i.e., zooming in), better accuracies in the elevations and georeferencing, and higher rates of variation demand closer spacings. Because these interact in complex ways, there is no general rule for the best spacing. As a start, though, you can expect that any spacing finer than the raster cellsize is not going to buy you much. Thus, if you can afford to compute the elevation profile using this relatively tight spacing, you might as well go ahead and do that. It might be overkill, but so what?
Note that such methods at best will accurately reproduce the interpolated elevation values. These almost always are a degraded version of the elevations the raster is representing. For example, many DEMs in mountainous areas do not attain the heights of the peaks, because the peaks usually fall between raster cells. When you interpolate between the sub-peak elevations, you usually get some kind of weighted average, which will still be less than the peak height. Thus, the elevation profile of a path passing exactly over a mountain peak will rarely reach the peak elevation. (Cubic convolution and some forms of kriging (including stochastic simulation with kriging) can overcome mild forms of this problem. Look to them if you want to reproduce the statistical characteristics of the elevation profile rather than settling for a "best fit" that averages out the extremes.