This phrase, which sounds the same however it is written, can be spelled in two ways - bran-new and brand-new. Two etymological explanations exist, one for each spelling.
The Oxford English Dictionary, which is authoritative, says that it should be spelled brand-new (although the other spelling is a much-recorded variant). The origin is the word brand, in an archaic sense of 'fresh from the furnace', or 'from having been burnt (i.e. newly melted and cast)'. (Sere also burn.) The earliest use seems to be 1570.
An alternative explanation was taught at schools in the twentieth century. It is attractive, so is repeated here - mostly to warn you against it. We were told that the original image was of something that had been bought recently, and was still in the condition in which it had come from the shop - not yet unpacked. In the old days, fragile goods were carried wrapped in bran (a waste product of milling) to protect them. This explanation is wrong.