Here is a delightful video of the inner workings of a spring-driven walking doll courtesy of the good folks at The House of Automata.
The Autoperipatetikos (meaning "walking-about-by-itself" in Greek) was invented by Enoch Rice Morrison and patented in 1862. Though it certainly wasn't the first mechanical walking figure, it was among the first American toys to be sold in Europe. To that point, most mechanical originated from Europe.
You can read more about the Autoperipatetikos in Mary Hillier's book Automata & mechanical toys: An illustrated history.