We derive congruences for various sequences involving binomial coefficients. In particular, we are able to prove some conjectures of Benoit Cloitre. Our methods include combinatorial techniques and the use of Lucas' Congruence. Surprisingly, the Thue-Morse sequence from combinatorics on words makes an appearance