Issue Tracker or Defect Stories?

You're starting up an Agile project using User Stories as your form of a work package.  Inevitably, the question will come up:

What about bugs? Do we use a bug / issue tracker? Or do we create a new story for it?

Key Considerations

• Maintaining a single priority queue.  It should be clear to everyone how to answer the question: "what should I work on next?"  And this answer should be consistent.
• Administrative overhead.  We don't want to spend as much, or even more, effort administering the work versus actually doing it.

Solution Options

• Make everything a story.  Bugs are estimated and prioritised along with stories.  Bug / Defect stories may have a different, simpler structure.  Simple approach but potential for excessive overhead if there are a lot of bugs, which is itself an indicator of a more pressing problem.  
• Bugs are tags on existing stories.  For example, sticking a pink Post-It on the related story card.  This suggests that stories do not progress to Done until all associated bugs are fixed.  If this strategy is not chosen, then usually some sort of triage process is done to determine what will be done and what will be treated as work separate from the story.
• Track bugs separately to stories.  This typically means a bug-tracking system.  With a lot of bugs, a bug-tracking system makes data analysis and management easier.  Typical mistakes with this approach are mismatches with how stories vs bugs are sized and not coordinating prioritisation across both stories and bugs.

My Typical Suggestion

As long as a story is still in-process and not considered Done, I'd treat bugs as tags on existing stories.  Once a story is Done, then it depends on how much effort is required to fix.  If it's quick to fix, then just fix it, possibly recorded with a Post-It or in the issue-tracking system to analyse for process improvement later.  If it's a significant effort, then it's a new story and goes into normal prioritisation.

If we're dealing with a legacy system where we have a lot of, let's call them, unrelated bugs discovered during development, I would generally use an issue-tracking system.