An almost identical expression crops up in the Marx brothers' film Duck Soup. The sequence in the film does give an apparent clue to the origin. In the film, one of the brothers says "and the boy wins a cigar" after Harpo, crazy as ever, has played as if shooting down a clay pigeon.
The origin is in American fairgrounds, where a cigar was the prize for winning at some attractions, including, presumably, a shooting gallery. The related expression "close, but no cigar" , meaning "nice try" 'or "almost, but very good", relates to 'test your strength machines: the test was to hit a platform with a hammer,as hard as possible, the platform being connected to a weight which flew up a vertical column at the top of which was a bell which it hit, if the blow was hard enough .The harder you hit, the higher the weight flew.If you drove it to the top, you won a cigar. If you got close to succeeding, but failed, it was "close, but no cigar".