Origin

Gas cookers began to replace wood-burners around 1915, and the actual phrase was used by Hollywood radio comedians around December 1939, and then appropriated by gas companies to promote gas cooking from around 1941 onwards.

The phrase has been attributed to Deke Houlgate, who after working in the gas industry, wrote the line for Bob Hope.

Dictionaries

The American Heritage Dictionary of Idioms (1997) by Christine Amme says it's 1940s slang, and it:

... alludes to gas stoves, which began to replace slower wood-burning stoves about 1915.

Gas companies

American Gas Association monthly - Volume 23 (1941) offers an origin:

The expression "NOW YOU'RE COOKING WITH GAS" has bobbed up again — this time as a front page streamer on the Roper Ranger, and as the banner line in the current advertising series of the Nashville (Tenn.) Gas and Heating Company, cleverly tying gas cooking to local food products and restaurants.

"Now you're cooking with gas" literally took the gas industry by the ears around December 1939 — Remember? — when it flashed forth in brilliant repartee from the radio programs of the Maxwell Coffee Hour, Jack Benny, Chase and Sanborn, Johnson Wax, Bob Hope and sundry others. Gas men began to listen as they had never listened before, kinda hoping to hear more, yet not knowing whether to be glad or mad, dazed or dazzled by such widespread FREE publicity on TIME interpreted in terms of national hook-ups involving hundreds of thousands of dollars all told.

The same association's Proceedings - Volume 23 (1941) suggests several slogans to promote gas, and notes:

Even Hollywood has been using, for some time now, the expression "Now you're cooking with gas" to denote perfection.

The Pacific Coast Gas Association's *Proceedings* - Volume 32 (1941) wanted to cash-in on the phrase's popularity:

It is up to us to plan our activities so as to assure progress — so that people will say of us "Now You're Cooking With Gas!"

Gas age - Volume 88 (1941) says the phrase is already famous:

A smart angle in one piece of copy was to capitalize on the now-famous colloquialism. "Now you're cooking with gas."

Deke Houlgate and Bob Hope

Houlgate College Football Rankings was founded by Deke Houlgate. On their website, his son writes:

During his days with the American Gas Association, before induction into the Army Air Corps, he originated the phrase, "Now, you're cooking with gas!" and planted it with Bob Hope's writers. They, in turn, wrote it into one of his radio scripts and put it into the mouth of comedian Jerry Calonna [sic], who made it nationally famous.

It was earlier attributed to Bob Hope, for example in the New York Times (April 10, 1941) review of his film Road To Zanzibar:

Farce of this sort very seldom comes off with complete effect, but this time it does, and we promise that there’s fun on the Road To Zanzibar. This time, as Mr. Hope puts it in one of his pungent phrases, they’re cooking with gas.

And a 1942 newspaper article (The Pittsburgh Press - Oct 15, 1942) refers to:

That famed Bob Hope wisecrack, "Now you're cooking with gas"...

More

A post to jackbenny.org says:

Just the other day, I heard a skit from "Good News of 1940" where Lou Holtz and Fanny Brice are among the "British" characters, and "Now we're cooking with gas!" is one of the lines.

It was common enough to confuse "word experts", notes Municipal sanitation - Volume 11 (1941):

"Coney Island" became a word in the University of Chicago's new dictionary, but terms like "now you're cooking with gas" and "that ain't the way I heard it", used by the people who frequent Coney Island continued to confuse word experts.

It was used in a 1942 film, The Big Street:

Florida Doctor: Did you ever hear of a thing called paranoia? No, I guess you didn't. Well, it's what happens to people when they get to believe they're something they're not.
Nicely Nicely Johnson: Now you're cooking with gas.
Violette Shumberg: Shut up, Nicely.

And the last lines of a 1943 Daffy Duck cartoon, The Wise Quacking Duck:

Daffy Duck: [in the oven] Say, now you're cooking with gas.

Wikipedia also says this cartoon, shortly before the end:

The war continues through some parts of the cartoon, including a fortune teller (referring to Jerry Colonna).