Velocity is a notion from ExtremeProgramming that helps calibrate a plan, tying broad statements of effort into elapsed time. Velocity is a statement of how much stuff a team (or a person if it's personal velocity) gets done in a time period. You should usually determine velocity by measuring how much got done in past periods, following the principle of YesterdaysWeather. A typical approach is to average the velocity the past three time periods to determine velocity for future time periods. Velocity has spread far beyond its XP roots and is now used widely in agile projects of all flavors.
For example, a team is working in two week iterations and estimates effort for stories using StoryPoints. In its first three iterations its velocity was 22, 30, and 27. We would then say the velocity of the team is 26. To use this for future forecasting, we might add up all the stories we hope to complete for the first release, let's say that's 330. We can then say we forecast that, given the current plan, we will be able to release in 26 weeks time. (330 / 27 => 13 iterations).
Velocity is a tool for calibrating estimations for YesterdaysWeather, it is not a measure of productivity. Different teams will use different baselines for their velocity units, so it's stupid to compare teams based on their velocities: there's no such thing as StandardStoryPoints. Similarly velocity is a team measure, not an individual measure. Using velocity as a productivity measure kills agility.
Velocity is commonly used with fixed iterations, but you can use the same idea with Kanban based planning. The amount of effort you get done in the last few weeks can be extrapolated the same way to come up with a forecast for future effort.
Velocity is a useful tool for estimation, one that's considerable less complicated to use than techniques I observed in the 80s. However, as with any estimation technique, it can be misused - you must always think about the PurposeOfEstimation.
I wrote a first version of this bliki entry in 2004-05-10.
Most books on agile development will talk about planning and thus mention velocity. The tasteful green book has an early, in-depth descrption of velocity from Kent and me. The ThoughtWorks ebook on estimation covers how velocity can be used with story points and story counting.
You can still find our initial explanation of XP planning terminology on the wiki.