Some thoughts to supplement Joachim's answer. Almost any foldable material can be used, but different characteristics are better for different purposes. You will want different material for an intricately-folded animal, say, than a simple, sturdy box. And if you want to dabble in curved folds, you generally need a stiffer material that will take and remember the creases. The size of the model also affects the required paper -- tiny models usually require thin, crisp paper while large models need heavier paper to hold the shape.
Heavier, stiffer media may require pre-scoring to get clean folds. In a material like the heavy plastic sheet in Joachim's polypropylene example, the fold lines are often embossed into the material to create a thin area that acts like a hinge.
Here are a few additional household materials that can be useful for origami:
Kraft paper is available in wide rolls for larger projects. You can also cut large pieces from paper grocery bags. Grocery bag stock is typically cruder than kraft paper, so it's more suited to models that don't involve intricate folds.
Newsprint/newspaper is available in large sheets, but it's crude paper that isn't particularly strong. Still it can be used for some models if you're careful.
Wrapping paper is another that's available on wide rolls. It tends to be thin but reasonably strong. It's also colorful.
Tyvek can be interesting for some models. You can cut it from shipping envelopes. At least one side is typically white with a little texture, which can look cool in a model. It starts reasonably stiff, but gets soft if it flexes too much, which can make it messy to create creases only and precisely where you want them. It does better if you pre-crease it.
Label wrapping on plastic soda and juice bottles is typically a plastic film that is brilliant white so the printing pops. It's opaque and the backside is still white. You may have to work a little to get it to take and keep a sharp crease, but you can get some interesting results. This was folded from the label on a cranberry juice bottle:
Manila folders are made from cardstock, and even after the tabs get tattered, the folder faces are often still in good shape. Trimming off the tabs and fold scores of waste folders still leaves a large sheet of cardstock that can be good for things like sturdy boxes and curved-folds. Here's an example from an old manila folder:
Aluminum beverage cans provide a good source for some kinds of projects. Joachaim's answer mentions sheet metal. Typical sheet metal is tough to work with, but aluminum sheets cut from beverage cans is something anyone can work with after minimal practice. Using the exterior surface provides a fun, recognizable pattern. Using the interior surface provides a brushed metal look.
Note, though, that this material is brittle; it can be bent and re-bent only a few times before breaking, and requires pre-scoring for clean creases where you want them (although there are a few experts who manage to do it without pre-scoring, directly on the empty can).
Beverage can sheets also take embossing well, and some people combine these to make things like embossed origami boxes:
Source: Making Boxes From Soda Cans
Beverage can sheets also handle curved folds. For example, I've seen the Hans-Werner Guth "Jump" design made from these sheets and it looked like a metal sculpture. I can't lay my hands on a picture of that result, but for reference, this is the design I'm referring to:
Just for completeness, some people focus on folding origami figures from currency (money origami or dollar-bill origami), because it's novel and the high quality paper is a good medium. Needless to say, the media makes that an expensive hobby.
Source: DIY Money Origami