Now You're Cooking With Gas

Where did this phrase come from?

Just a guess:
Your phrase means to do some thing or some task the right or more efficient way.
Natural gas distribution and usage channels were installed in the New York City area and, I guess, other major population centers somewhere in the mid to late 1800s.
The change to gas for cooking and lighting was a major big-time advancement which resulted in your phrase.