'Up a storm' has been an American colloquial phrase since the 1950s. The earliest use of 'cooking up a storm' actually referred to cooking...ie the preparation of food. Since the early days, however, it has taken on the figurative meaning of doing anything with enthusiasm, as in 'the band was playing up a storm' or 'I plan to shop up a storm'.
I should have added above that 'cooking' can be used to replace the words such as 'playing' and 'shop' in my examples above. In other words, one might say 'The band was 'cooking up a storm' to mean 'playing' enthusiastically rather than actually 'cooking'!
I guess the thinking behind this vaguely suggests a witch calling up a storm. As QM says, the word cooking has its own metaphorical uses - 'now you're cooking!' - which may suggest you're getting hot like an engine that's warmed up and going places. So 'cooking up a storm' may be two idiomatic phrases in one.