I don't know of any rule that says a carbon copy must or must not be on headed paper.
The term "carbon copy" has come to mean an identical copy, but this can be confusing.
Carbon copies were originally made using carbon paper. This carbon paper was sandwiched between two sheets of paper. When pressure was applied to the top sheet (either with a typewriter or a pen, or later with a dot-matrix printer), this caused carbon to be transferred at that point from the carbon paper to the sheet below. The result was a nice-looking original, and a rather smudgy copy, the "carbon copy".
These days we don't use carbon paper; we can cheaply and efficiently print out several copies on a laser or inkjet printer, or we can photocopy. The abbreviation "cc" is now often taken to mean "courtesy copy".
It may sound obvious, but a copy is not an original, and so doesn't have to look exactly like an original. If something is cc'd to you, that means that it's sent to you for your information only, and you're not expected to act on it. This might typically happen within a company: I might, for example, send you a letter confirming some arrangements for a working lunch, and send a cc to my boss. Obviously, professionalism dictates that you get a nice, clean, beautiful, multicoloured original, but my boss will be quite happy with a black-and-white photocopy.