The first record of "Hayfoot, strawfoot" is from the early 1800s; an officer of that times tells the story about his use of it (apparently one of his tales about his (presumed)ignorant recruits). The story was transferred to New Hampshire volunteers in the Revolutionary War, and to the Civil War as well. The story probably goes back to at least the Roman legions and their soldiers from among the Scots, Spanish and others.