I can show that $S_7$ is the smallest candidate for the property given. And, with a little calculation, I think it works out - $(1234)(567)$ and $(14)(23)(57)$ seem to generate such a subgroup. But I was wondering if there's a more clever way of approaching the problem. If so, is there a general strategy that works for a given $D_m$?
Every dihedral group is generated by two elements of order 2. And every group generated by two elements of order 2 is dihedral. Furthermore the order of the generated dihedral group is the order of the product of the two elements. So if x,y each have order 2, then is dihedral with 2*n elements where n is the order of x*y. This is why dihedral groups show up so often in finite group theory, anytime you have a group with a lot of elements of order 2, you have a lot of dihedral subgroups.
A permutation has order 2 only if it is a product of 2-cycles, so it looks like (ab)(cd)(ef)... So your question is equivalent to "What is the smallest n such that there are two products of 2-cycle swaps on n elements, and the product of those two permutations has order 12?" There's still a search involved, but its a smaller set of permutations to search.