The simple formula is just the first-order expansion of the more complicated one about $v = 0$, the latter being exact for the Doppler effect of motion purely along the line of sight. The $v$ here refers to the peculiar motion of the galaxy.
Be aware that for all but the very nearest galaxies, the observed redshift comes almost entirely from the expansion of the universe, not from relative motion in the special-relativistic sense. Thus converting from redshift to velocity using either of the formulas mentioned, though a very common practice, can be misleading. For a thorough albeit technical discussion of subtleties related to this point, there is a paper by Davis and Lineweaver.
Edit: Since I have lately been using NED a lot, I came across this page in their documentation. Point 1 in particular notes that "no relativistic correction is applied" and so you may see "velocities in excess of the speed of light." (It also says $v = z/c$, but I hope that's just a typo.) There are two important points here. The first is that you can safely assume the values reported are redshift times the speed of light, possibly with a correction to a certain reference frame. The second is that even NASA is under the misconception that redshift of distant galaxies has something to do with Doppler shift, when this is just fundamentally false. The quantity $zc$ is really just a way of putting units to redshift, nothing more.