Good newbie instructions for creating minimal complete bug examples?

It's all in the name. A complete minimal example is an example that is complete and minimal. Complete means that it contains all pertinent information, and minimal means it contains no information that is not pertinent. The ability to identify what is an is not relevant is something that only comes with practice - trying to provide instructions for this seems a little like trying to provide instructions on riding a bicycle. You can give the technical explanation and describe the mechanics (and the TeX FAQ you linked to does that very well) but in the end the only way to really learn is by doing.

I'll start this off with the ones I'm familiar with; these both come out of the TeX community, and so are a little oblique for programming. I'm hoping other people have better answers.

The TeX FAQ has an entry on How to make a “minimum example”.

That page points to a somewhat longer article on "What is a minimal working example?". Again, this is for TeX documents; the ideas are the same, but the tools and details a little different.

Edit (2013/01): Another one that I noticed in a StackOverflow comment: The "Short, Self Contained, Correct (Compilable), Example" page. Not perfect, and it suggests 20kb (!) as an upper limit, but a good addition to the list.

Edit (2013/02): Jon Skeet has a blog post about writing good questions, which includes a section on sample code that seems useful.