Origami includes many genres: one uncut square (the most common form), many uncut squares (which takes in both modular and composite origami), triangles, rectangles, even the occasional slitted shape. The common element of origami is that folding is the primary means of creating the form. And it's usually paper. But not always.
In fact, many materials can be folded using the techniques of origami; all that is required is that the material come in sheets and that it can form creases. Within that broad category, a wide range of materials have been folded over the years with results that are novel, interesting—and sometimes even delicious.
Cloth would seem an unlikely subject for origami, because most cloth won't take a crease. But in fact, there is an entire genre of origami that uses cloth: napkin folding. Many people have probably attended formal dinners where the cloth napkin was folded into a bird-of-paradise or other decorative shape. This version of the art goes back hundreds of years in Europe; it is mentioned in a book, "Il Trinciante" by Vincenzo Cervio which was published in 1581! (There is no known connection between Renaissance napkin-folding and the Japanese paper-folding tradition, but cloth napkin folding is arguably as old as the Japanese art of origami itself. Origami researcher Joan Sallas has traced European napkin folds back to the 1600s, including the first recorded use of the terms "Mountain Fold" and "Valley Fold" in this context.)
Today you can find many books and articles giving techniques for folding napkins into various decorative shapes. All that is required is a fairly heavy, stiff cloth, like a linen napkin. Even so, such material does not hold creases very well, and only relatively simple shapes can be folded therefrom. Starching a cloth makes it stiffer and more able to hold a crease, and more complicated forms can be folded. (Not too surprising; adding starch to cloth to make it stiffer is analogous to adding sizing to paper to make it stiffer.) Samuel L. Randlett's landmark book, The Art of Origami, showed several plates of elaborate pleated forms created with starched cloth. In more recent time, origami tessellation artist Chris K. Palmer has created elaborate patterns of intersecting pleats in thin raw silk, patterns reminiscent of Moorish tilings. Chris's technique, using tiny stitches to gather and hold the pleats while using steam and pressure to set the folds, is described in his book, Shadowfolds. This is similar to a technique uncovered by Eric Joisel, which has been practiced by F. Ciment Pleating, a family firm for over a hundred years. In their approach, cloth is sandwiched between two sheets of paper; the entire sandwich is pleated in an elaborate pattern, then pressed and steamed to set the folds; then the paper is peeled away, leaving the pleated cloth form.
Cloth napkins are now only seen in formal settings; they have been replaced by paper napkins in everyday life. Not surprisingly, many of the folds suitable for cloth napkins can be replicated with paper ones. But there are also folds that are especially well-suited to paper napkins, which makes them also good folds for impromptu demonstrations of origami when there is nothing else around. One of my favorites is Vincent Floderer's Mushroom. (Alas, I am not aware of any published instructions for this, but Vincent is a common presence at origami conventions and frequently teaches it in his workshops.)
All this talk of dinner settings leads naturally to the next novelty material: edible origami. The general rule of origami is, if a material is sheet-like and accepts a crease, it can be folded into something. Sometimes, it can be eaten, too!
Edible sheets for origami should be thin, of course, and flexible; many materials meet these criteria. The tougher criterion is that it should take a crease. Most edible sheets are not very forgiving of creases. Flour tortillas can be folded into simple shapes if they are steamed first; otherwise, they tend to crack. I have also heard of people using won ton wrappers for folding. One of the more interesting, but finicky materials, is phyllo pastry, which is extremely thin, but becomes incredibly brittle once it dries out. It also tears easily in one direction; for that reason, when I've folded from it I use two sheets. The first is laid down, brushed with melted butter (which acts as a glue), then the second sheet is laid crosswise. The resulting sandwich is cut to square and folded—quickly, before it dries and cracks. The folded figure is then baked to a light golden brown. (Baking is also the appropriate finishing treatment for tortilla folds.) In general, simple folds work best, like flowers or geometric shapes. However, a particularly impressive display comes from folding the aforementioned phyllo sandwich into the traditional Japanese crane. Other edible materials can be folded; I've had some fun with "fruit leather" (although it tends to stick to itself). I should also mention David Lister's discussion of icing sugar origami. The nice thing about all of these materials is that you can eat your mistakes.
Origami artists are familiar with folding metal as part of foil paper or tissue-foil laminates and their ilk. While these materials include paper as part of the sandwich, it is also possible to fold metal directly. The closest to traditional paper folding is to use thin foil, such as household aluminum foil. It is very difficult to fold this material neatly, however; all but the simplest origami from foil ends up looking wrinkled and cluttered. (The paper in foil paper or laminates provides much-needed stiffness that helps resist small-scale wrinkles.)
Heavier-gauge metal resists wrinkling better and provides a sturdier folded product in the end. However, it is harder to work with and only simple shapes can be folded. One artist, Joe Spears, has found an elegant solution; he creates origami shapes from heavy-gauge steel, cutting them apart into facets and then welding the facets back together along the folds. Another artist, Lane Allen, has developed a folding style he calls "origane," based on folding from metal mesh. The mesh can be folded into surprisingly complex shapes and can be curved like wet-folding, but provides substantial structural rigidity (and a pleasing heft).
A third possibility is to fold from paper and then replicate the folded shape in metal, which is how I and my collaborators created my origami bronze and stainless steel metal sculpture. The origami figure can be folded from any type of paper, then a mold made from it, either directly, or using the lost-wax (or rather, lost-paper) process. If you use the latter process, you should be sure to use an all-cellulose paper, not a clay-coated paper, as the latter will leave inorganic residue in the mold after it has been burned out.
As you can see, origami artists have been an inventive lot over time, and this discussion has only begun to touch on the materials that can be folded. For commercial design work, I've also folded shapes with Kapton, Mylar, and other polymer materials. For another take on the assortment of materials that can be folded, see David Lister's essay on folding materials on the BOS website.