What is the most efficient way to test whether a set $X \subset \{0, 1\}^n$ and its complement $\{0, 1\}^n \setminus X$ are linearly separable? I am interested in algorithms that have optimal running time, and ideally which are also very easy to implement.  If you can also give some tips on how to implement the algorithm(s) you mention in the answer, that would be great.
Actually, no algorithms, efficient enough for you to be interested in, are available. Your problem is exactly the membership problem for the class of linearly separable boolean functions (which are the indicator functions of your sets), and it is known to be co-NP-complete.