What you are dealing with is interpolation techniques. That is, you have two data points, and need to estimate the value of a point in-between. There are many such available, but the three main ones for the kind of raster processing you're looking for are:
Nearest Neighbour: it'll simply take the value of the closest data point, and replicate it. So, if we have point A as 5, and point B as 13, a point C that is 25% the way between them will receive value 5, as it's closer to point A.
Linear: it creates a line passing between both points, and the finds a value along the line. So, same as the example above, a point C that is 25% the way between A and B will receive a value of 7.
Polynomial: similar to linear, but instead of a line, it creates a polynomial function between the two points, and estimates the in-between value along the way. So, the same example might yield a value of, say, 6.72, or 8.11, depends a lot on the function.
Cubic interpolation is one form of polynomial, spline is another. The terms bilinear and bicubic simply mean as a linear or cubic interpolation for 2-dimensional data (such as a raster). This picture below illustrates well the three methods:
Now, to your question: what does this mean when dealing with a DEM? Or, better yet, how do each affect the processed image?
Specifically, nearest neighbour will always generate you values that were already in your source data. You garantee that these values all exist somewhere at your object-space, so you won't get values that are nowhere to be found, but it's also quite likely that your values are at least a bit wrong, as they were only correct for their original location. This means that, in a DEM, with NN you retain the general shape of your terrain, as the relationship between adjacent pixels is preserved, but you should take your values with a pit of salt. Also, your generated raster can look quite "blocky" as a result.
As for linear and polynomial, they make better guesses at intermediary values given a tendency (linear uses local tendency, whereas polynomial take into account the tendency of a larger area), which likely produces more correct values overall, but can also distort the shape of your terrain (everything will look more continuous, even when it's not). Also, due to how the algorithms work, you may lose absolute information about peaks and valleys (linear may generate less extreme values for each, whereas polynimal more extreme; so, a peak at 1800m might appear to have 1790m with linear, whereas 1820m with polynomial). It looks nicer than NN, with cubic looking the smoothest.
Conclusion: there isn't a rule set in stone as to which should be used, you really have to study your data and your goals beforehand. In general, I'd say that, if you have a more rugger terrain and wish to retain its overall form, or if you have the need to retain absolute values from the source data, you might want to use nearest neighbour. If having overall more correct height values, or looking nicer, is more important to you, then either linear or cubic. Splines should be used basically to make things looks nice, but are less statistically sound.
As a side note, for highly accurate work, it's common to use bilinear or bicubic while taking care of its downfalls. These are, specifically, the use of control points for retaining a few key absolute values, and breaklines for indicating where a terrain should have a steeper transaction. This is, however, usually done in photogrammetric software, not GIS (though ArcGIS does have limited breakline capabilities through its 3D Analyst extention).
EDIT: specifically for generating the least errors in values, I bring notice to this ISPRS article on accuracy comparison of interpolation techniques. I'll jump to the conclusion, but you might want to read it in full nonetheless: both bilinear and bicubic yield the best results, and are statistically indistinguishible, accuracy-wise. Also notice that the article too brings up the necessity of using breaklines for steep changes in height.