I get this questions often. I am sure you probably also got this question at one time or the other. There are two ways to look at this- value vs. cost. These perspectives are linked to how you define velocity. Let's look at both in more details.
Value perspective. If you define velocity as the net value (in story points) delivered to your customer, then you should not include bugs in your calculation of velocity. Think about it for a moment. Bugs are something that are not working as expected, but the customer has already paid for them. So, by fixing bugs you are not really delivering any "incremental value" to the customer. If you increase your velocity by including bugs, you are inflating your velocity. Now, granted that sometimes we report something as a bug when it is an incremental feature. You need to work with your product owner to negotiate to change those bugs into stories and account your effort for them in your velocity.
Cost perspective. If you define your velocity as the amount of work done by a team in a sprint, then you should include bugs in calculating velocity. Yes, bugs take effort and time to fix. Hence there is a cost associated with fixing bugs. But this makes the release planning a little bit complicated. Because you cannot know ahead of time how many bugs you may have until the release. Directly using velocity to calculate the effort or to determine the time-line for the release will most likely be off (undershoot). One way to address this is to break the velocity into two components- feature-delivery velocity, and bug-fix velocity. This is in a way going back to the first option.
I personally am in favor of using "value" perspective and exclude bugs from calculating velocity. This helps keep our eyes on the ball- delivering "customer value." As a result, we are encouraged to reduce bugs in the first place so that we can free up our capacity to deliver more value. That is why we currently do not allow users to point estimate bugs in ScrumPad.
Are you including your effort spent on bug fixing in your velocity?