A vertical datum is used for measuring the elevations of points on the earth's surface. Vertical datums are either tidal, based on sea levels, or geodetic, based on the same ellipsoid models of the earth used for computing horizontal datums.
In common usage, elevations are often cited in height above sea level; this is a widely used tidal datum. Because ocean tides cause water levels to change constantly, the sea level is generally taken to be some average of the tide heights. Mean lower low water — the average of the lowest points the tide reached on each day during a measuring period of several years — is the datum used on most nautical charts, for example. While the use of sea-level as a datum is useful for geologically recent topographic features, sea level has not stayed constant throughout geological time, so is less useful when measuring very long-term processes. In some situations sea level does not apply at all -- for instance for mapping Mars' surface -- forcing the use of a different "zero elevation", such as mean radius.
A geodetic vertical datum takes some specific zero point, and computes elevations based on the geodetic model being used, without further reference to sea levels. Usually, the starting reference point is a tide gauge, so at that point the geodetic and tidal datums might match, but due to sea level variations, the two scales may not match elsewhere. An example of a gravity-based geodetic datum is NAVD88, used in North America, which is referenced to a point in Quebec, Canada. Ellipsoid-based datums such as WGS84, GRS80 or NAD83 use a theoretical surface that may differ significantly from the geoid.
On nautical charts, depths of water are relative to chart datum which is generally the lowest tide caused by gravity alone.