Let H be a subgroup of G. (We can assume G finite if it helps.) A complement of H in G is a subgroup K of G such that HK = G and |H∩K|=1. Equivalently, a complement is a transversal of H (a set containing one representative from each coset of H) that happens to be a group.
Contrary to my initial naive expectation, it is neither necessary nor sufficient that one of H and K be normal. I ran across both of the following counterexamples in Dummit and Foote:
It is not necessary that H or K be normal. An example is S4 which can be written as the product of H=〈(1234), (12)(34)〉≅D8 and K=〈(123)〉≅ℤ3, neither of which is normal in S4.
It is not sufficient that one of H or K be normal. An example is Q8 which has a normal subgroup isomorphic to Z4 (generated by i, say), but which cannot be written as the product of that subgroup and a subgroup of order 2.
Are there any general statements about when a subgroup has a complement? The Wikipedia page doesn't have much to say. In practice, there are many situations where one wants to work with a transversal of a subgroup, and it's nice when one can find a transversal that is also a group. Failing that, one can ask for the smallest subgroup of G containing a transversal of H.