What is the difference between the two, and when should I use one or the other? I have seen "stratagem" used to describe "under-the-table", or negative/sinister strategies. Is this true in general?
According to the Grammarist, the two terms are not synonymous. The strategy is the more conventional way of approaching the problem whereas the stratagem is the unproven or unconventional approach. The way that you describe "under-the-table" falls under the definition of stratagem as opposed to strategy, as it conveys the use of unconventional (under-the-table) tactics. So yes, your statement is true in general.
I want to say that strategy is the design and stratagem the execution thereof.
In information science, a class or design is the abstract of an actual instance of implementation of that class or design.
The Maserati Hybrid is a design, but no such car has been built. Regardless that enthusiasts could discuss and argue over the Maserati Hybrid as though it were an existent car.
Perhaps Maserati in their secret lab garage does have an actual hybrid to that design. Then that particular car is an instance of the design. So the engineers discussing about that particular car is not the same as enthusiasts arguing in forums over the design of such a car.
When you speak of the Honda Civic Hybrid, it is merely a class of cars. However, if you supplied a VIN, then the particular car id'd by that VIN is an instance of that class.
One can speak of strategy, without ever implementing or executing it. When one speaks of stratagem, it is an implementation or actual execution of a strategy.
One can speak of theory. But a theorem is an actual instance of theory grounded in postulates.
One is imaginary or subjunctive, the other is real or implementation.
However, since usual people aren't usually abstract enough to differentiate between theory and practice, between design and instance, stratagem could coincide in intentional meaning with strategy. People would speak of the Honda Civic Hybrid as though it were an actual car.
A wise yogi once said, In theory there is no difference between theory and practice, but in practice there is.
BTW, he also said something like, No one goes there anymore, it is too popular.