How stable should velocity be?

If you are estimating story size instead of duration, velocity is what will allow you to determine project duration and thus cost. In such an environment, velocity is an important metric and needs to be monitored accordingly.
As I wrote back in April, we have been collecting data to see if we were improving or not our velocity. My original intent was to find what influenced velocity however, that goal became making sure that velocity is somewhat stable.
As we started to collect metrics (Total # of team hours available, # of points with clear definition of done, # of distractions and # of blocks) we started to pay more attention to velocity. It was interesting to see that velocity was varying beyond what we expected. We could always explain why velocity went up or down, but it was varying regardless. One of the issues we found was that story estimates were wrong. The team inadvertently started using a different scale that turned out to be too small. In other words, a story that used to be a 5 became a 1, so the stories that were a 1 had nowhere to go.
If you are using story points, you need to make an effort to make sure that the relative sizes of stories are valid. As you work through your stories you look for stories with disproportional sizes. A story of size 5 must be a little bigger than twice a 2.
I regularly use a room painting problem to explain story points. It works well because people will tend to estimate the time it will take to paint a room by the number of walls and their sizes, but the number of cuts (windows, doors, etc.) is what really determines how long it will take. So once we go through the exercise of estimating painting multiple rooms based on sizes, I introduce the cutting variable and thus have the team re-estimate the "project". In other words, when the team learns something new about a set of stories, they should go back to the backlog and re-evaluate their estimates.
During this effort of collecting metrics, I did create control charts for velocity, but these weren't as useful as I expected. If you just observe velocity you can already tell when there's a problem, you won't need control limits for that. Pay attention to what is contributing for your velocity to vary. If it is distractions, make sure they go away!
The participation of the team is important. They have to share your ideal that this is intended to help them achieve their full potential and that cheating the system will not help anybody.
Velocity shouldn’t swing much in a single iteration. It should be stable and somewhat predictable. If it does you have a problem and need to address it.