"Claymation" is an abbreviation for clay animation, the practice of creating stop-motion animation using colored plasticine clay figures. It's actually trademarked today (more about that later), so I'll be using the generic term "clay animation" for most of this writeup.
Clay animation is rarely done because of the time requirement: animation is typically done at 24 frames per second, making the constant reshaping of figures a time-consuming process. To speed things up and avoid the problems of distorting parts of the characters, the technique of swapping out clay parts -- such as talking mouths on a stationary head -- has become common. Purists may argue this isn't truly animating the clay, but the improvement is so immediate it's hard to complain.
So when did it first appear? Clay's been around a long time, of course, but not until plasticine was invented in 1897 did animators have a practical tool for creating attractive, poseable characters. About ten years later, in February 1908, the first known film using clay animation was released. Entitled A Sculptor's Nightmare, it was a spoof on the 1908 presidential election and featured a slab of clay "morphing" into a bust of Theodore Roosevelt.
Stop-motion animation using models appeared again in the coming years (King Kong being the most memorable example), but not always using clay. In the mid-1950s Gumby and Pokey appeared on television, created by Art Clokey for Hanna-Barbera studios. Their attractively simple children's show reigned for years following its introduction in 1956. The nature of the animation gives Gumby a certain timelessness; you can still find it in syndication today. I'm pretty sure you can find pr0n parodies of Gumby and his hapless cohorts on the Internet these days, which is probably a testimony to their status as pop icons.
Meanwhile, December 1964 saw the arrival of the still-popular animated Rudolph the Red-Nosed Reindeer holiday special, soon followed by Frosty the Snowman and others. The Academy Awards changed their "Best Cartoon" category to "Best Animated Film," opening the door for clay animation to win international recognition. Mr. Bill (who was more of a parody of animation) appeared on Saturday Night Live and, if you're going by sheer video sales, remains the most popular SNL character today.
Then Will Vinton arrived. In 1974 a clay animated film co-created by him, Closed Mondays, won the Academy Award. Shortly thereafter, Vinton trademarked "Claymation" and established Will Vinton Studios. He got right to work. In 1985, he produced and directed The Adventures of Mark Twain, which at 72 minutes was the first feature-length, "100-percent clay" animated film. Vinton was also responsible for creating the ridiculously popular animated California Raisins for an advertising campaign. In 1987 he completed a documentary simply entitled Claymation, explaining the process his studio used.
Not that the rest of the world's animators were sitting still. Animation festivals around the world were already underway, with plenty of clay showing up every year. Music videos employed it to make things just a little more surreal. The British Nick Park first made himself known in 1990 with Creature Comforts, a short independent film about zoos from the animals' perspective. Following that he created Wallace and Grommit for Aardman Animations, and each of his three short films featuring these characters -- A Grand Day Out (1992), The Wrong Trousers (1993), and A Close Shave (1995) -- received an Academy Award. Their success led to the creation of Chicken Run in 2000.
And so it goes. Clay animation, by its very nature, will probably never benefit from the introduction of new technology as the years go by, only from the ingenuity of the animators. It's slow, it's tedious, and even modern creations are more than a little reminiscent of the old Gumby shows. It looks simple until you take the time and attention to detail into account, at which time almost nobody wants to touch it. But maybe that's why everybody takes notice when it reappears. Doing it well is an art, there's no question about that. Very few people bother with it unless they intend to do it well.
A book by Michael Frierson entitled Clay Animation: American Highlights 1908 to the Present was published in 1994. Most of the above factoids originated in that book, so if you want to know more, give it a lookup.