I'm using implementation of Vincenty's algorithms, and I have their class called "position" that requires lat, lon, and elevation defined by: "Elevation above the surface of the ellipsoid".
What is the meaning in such applications? Is it just simple "Elevation above MSL"?
The elevation above the ellipsoid (ellipsoidal height) is the elevation above a mathematical model that approximates the shape of the earth. The current most common one is WGS84. These are the elevations that you'd get from a GPS.
Orthometric heights are measured above the geoid or equipotential surface, that is, the surface of equal gravity. MSL is "mean sea level," which is supposed to roughly approximate the equipotential surface, but obviously can't be directly measured inland.
Unlike the ellipsoid, the geoid can't be represented by a function is complicated (see 2NinerRomeo's comment), so conversions have to use a grid shift raster to find the ellipsoidal separation at any given location. NRCAN has a decent page describing this stuff.
If you have orthometric (e.g. MSL) heights, you'll need to transform them using the appropriate grid shift file.
An ellispoid is a mathematical model of the earth that approximates its three dimensional shape. See this definition. Elevation on top of the ellipsoid is 0, but since it's just an approximation one can be above or below the ellipsoid at any given point. "Elevation above the surface of the ellipsoid" is the distance between the measurement and the 0 value of the ellipsoid.
The Z value in a given coordinate system has to be based on something--a height above a generalized shape of the earth. MSL is one way to do it, but in my experience the majority of cases use ellipsoids as approximate figures. GPS, for example, uses WGS84 as the global coordinate system, and with it is the WGS84 ellipsoid.
An "ellipsoid" is a mathematical approximation of the shape of the Earth. Many different ellipsoids exist, but the two most widely used today are the GRS80 and the WGS84, which attempt to provide a best-fit across the globe. Heights were traditionally referenced to MSL, but with satellite and other technologies, we can often do better in terms of accuracy. HAE (Height above ellipsoid) is the term often used. (info summarized from Bolstad, 2012)
$GPGGAstream provides 2 sets of altitude data (WGS84 ellipsoid & MSL). It can be very confusing for people who aren't familiar with the two pieces of info. – Branco Aug 4 '15 at 19:39