The final stanza of the Star-Spangled Banner, written in 1814 by Francis Scott Key (and later adopted as the U.S. National Anthem) contains one of the earliest references to a variation of the phrase: "...And this our motto be: "In God is our trust."
Today, the motto is a source of some heated contention. One side argues that a need for a "separation of church and state" requires that the motto be removed from all public use, including on coins and paper money. They argue that religious freedom includes the right to believe in the non-existance of God and that the gratuitous use of the motto infringes upon the religious rights of the irreligious. They argue that any reference to God in public places is unconstitutional.
The other side of the argument states that the separation of church and state means that congress shall not impose a state religion on the populace, and that the separation of church and state is a legislative invention not intended by the founding fathers. They point out that religious language is used in the founding documents, such as "Nature and Nature's God" in the Declaration of Independence.
Interestingly enough, Theodore Roosevelt argued against the requirement of the motto on coinage, not because of a lack of faith in God, but because he thought it sacrilegious to put the name of Diety on something so common as money. This argument is rarely used by either side today.
Whichever side of the argument is ultimately victorious will be decided at some point in the future, either by judicial fiat, legislation or constitutional amendment, but at this point use of the motto on circulating coinage is required by law. While several laws come into play, the act of May 18, 1908 is most often cited as requiring the motto (even though the cent and nickel were excluded from that law, and the nickel did not have the motto added until 1938.) Since 1938, all coins have borne the motto. The use of the motto was permitted, but not required by an 1873 law. The motto was added to paper money over a period from 1964-1966.