The "wall of separation between Church and State" was not built overnight, and the Establishment Clause of the First Amendment was just one brick.
The Establishment Clause did not apply to the States. An establishment of religion, i.e. direct tax aid to churches, was the situation in nine of the thirteen colonies on the eve of the American revolution. Rhode Island, New Jersey, Delaware, and Pennsylvania had never had an establishment of religion. After the Declaration of Independence, the new states began writing constitutions, usually abandoning state-sponsorship for a particular religion or sect, and by approximately 1791, nine of eleven states that ratified the amendments of 1789 had disestablished. In the New England, however, the process went on well into the 1800s: Connecticut in 1818, New Hampshire in 1819, and finally Massachusetts disestablished in 1833. Even after "disestablishment", some states persisted in tax-support for religion, by "general assessment" meaning the proceeds were available to all denominations.
The end of government tax support did not hurt religion in America. In fact, quite the opposite, it seemed to help, at least with "fringe" religious activity, previously suppressed by the state-supported established churches. Official disestablishment was followed by a wave of religious fervor, the likes of which were unprecedented. Revivalism swept the country, greatly expanding the Methodist and Baptist churches in America, and numerous sects were founded: Mormons, Shakers, Unitarians, Adventists, African Methodists . . . all got their start in the early 19th Century following the end of state-sponsored religion.
In 1830, one observer wrote:
I do not know whether all Americans have a sincere faith in their religion; for who can read the human heart? but I am certain that they hold it to be indispensable to the maintenance of republican institutions. This opinion is not peculiar to a class of citizens or to a party, but it belongs to the whole nation and to every rank of society.
Alexis de Tocqueville, Democracy in America, Tr. Henry Reeve
(London: 1835).
While current battles over the Establishment Clause generally involve schools, the current "hands off" approach to religion in schools developed much later than the adoption of the Bill of Rights in 1791. Disestablishment did not mean the removal of religion from schools. In 1838, the Pennsylvania legislature passed a bill requiring the use of "the Bible" (meaning the Protestant King James Version or "KJV") as a textbook in the schools. Pennsylvania was formerly one of the centers of religious tolerance, but by the late 1830's had become extremely intolerant towards Catholics. The change resulted from massive Irish Catholic immigration, fleeing the Great Potato Famine. By 1842 there was considerable strife about which Bibles children could use in schools --the KJV or the Catholic "Douay" version. Violent riots erupted in Philadelphia.
Anti-Catholic bigotry (known as "nativism") marked the period from the end of the Civil War until the Twentieth Century. Schools were often the battleground. On December 14, 1875, James G. Blaine, the former Speaker of the House of Representatives and soon-to-be-announced candidate for President, proposed what became to be known as the Blaine School Amendment. It provided:
No State shall make any law respecting an establishment of religion, or prohibiting the free exercise thereof; and no money raised by taxation in any State for the support of public schools, or derived from any public fund therefor, nor any public lands devoted thereto, shall ever be under the control of any religious sect: nor shall any money so raised or lands so devoted be divided among religious sects or denominations.
(Congressional Record, 44th Congress, First Session, p. 205).
Some states admitted to the Union after the war were required by Congress to incorporate such language in their Constitutions. For example, the New Mexico Constitution, (Art XII, ยง 3) adopted in 1911, prohibits the use of public land or money for "any sectarian, denominational or private school, college or university". In fact, however, many public schools in New Mexico, particularly in rural areas, were operated by the Catholic Church (just as they had operated for centuries). Public money was used to buy Catholic parochial school textbooks for New Mexico public schools well into the 20th century, until a lawsuit in the 1950's secured the end of the practice.
In the Twentieth Century, this "nativist" attitude gradually divested itself of its origins in bigotry, became a majority opinion, and was adopted in federal Constitutional law, culminating with the Lemon test, from the case of Lemon v. Kurtzman, 403 U.S. 602 (1971). The Lemon test holds that an act of government, in order to be constitutional, must (1) be primarily secular in purpose; (2) neither advance nor inhibit religion; and (3) avoid excessive entanglement with religion. In Lemon, the Court held that paying the salaries of teachers in religious schools, even though they were teaching secular subjects and not religion, fostered excessive "entanglement" with religion.
Sources:
Library of Congress: Religion and the Founding of American Republic:
http://lcweb.loc.gov/exhibits/religion/
Boston, Rob, "Bible Riots: When Christians Killed Each Other Over Religion in Public Schools", Liberty (May/June 1997)
http://members.tripod.com/~candst/boston3.htm