Christopher, 

some things are best explained as being ‘right’ because they are what would be said by a native speaker. Maintaining grammatically correct language use is not the only standard applied.

Just as it is usually unnecessary and therefore uncommon in English to say ‘ I bought a brand new shirt/dress/shoes/hat ‘ instead of just saying ‘ I bought a new shirt etc ’,  a native French speaker will usually and naturally say ‘ un nouveau chapeau ‘.

The ‘norm’ ( and hence implied message) is that some things, such as a hat, will be ‘ brand new ‘, although not necessarily your first ever purchase of such item. Additional information can and usually would be given if it is not ‘new new’ !

The adjective ‘ neuf ‘ is used to emphasise ‘brand new’ but does not need or have to be used when the assumption is that something is unlikely to be 2nd hand.