This one is an easy one. Cigars used to be given as prizes for fairground games. It was first recorded in print in the 1935 script of the film version of Annie Oakley. “Close, Colonel, but no cigar!” It started appearing widely in US newspapers from about 1949 onward (maybe a journalist was a fan of the old movie).