There were a few different mottos proposed Our God and Our Country, God Liberty and Law, Our Trust is in God, God Our Trust, and In God We Trust. One possible source of the wording of the motto comes from the fourth verse of the Star Spangled banner, "And this be our motto, In God is Our Trust."
And you folks have answered half his question, what the first coin was, but not the first currency was. That was the 1886 five dollar silver certificate. The motto wasn't mandated to appear on the note, but the reverse design showed five
Morgan dollars. One obv and four reverse were shown and the motto clearly shows on the reverses of the coins. The first note for it to appear on after it was made mandatory was some of the 1935 G series one dollar silver certificates. The 35 H series was supposed to be the first but both series were being printed at the same time and some (a lot) of 1935 G series notes were printed with a 35 G front plate and a 35 H back plate. The first Federal Reserve note to carry the motto was the 1963 series one dollar note.