How does the velocity of a galaxy depend on the distance from earth?

All points in space are receding from each other due to the expansion of space. A galaxy will have a radial velocity (outwards from the earth) which is linear with the distance from the Earth. This is how we can use redshift to determine the distance that a galaxy is at.

You need to remember that this is an average effect, and some objects may well be moving towards Earth or in some other way due to their local velocity which is caused by some previous interaction.

The expansion rate that Capuchin refers to comes from Hubble's Law. Edwin Hubble was the first person who realized that there is a relationship between the velocity that galaxies are receding form our own (as measured by the galaxies' red shift) and their distance. The currently accepted value for Hubble's constant is about 71 Km/sec per MegaParsec. And as Cap notes, some nearby galaxies like Andromeda ar actually moving closer to us, because they are close enough that the effect of Hubble's Law can't overcome their local motion, One other item of note - if you take the inverse of Hubble's constant you get a reasonable approximation of the time since the big bang - about 13 Billion years.