When most people think of origami paper they probably think of the kind found in any arts and crafts shop - thin, smooth, multicoloured on one side and cut to squares. This type of paper is called 'kami'. Kami is the Japanese word for paper but is used in English in this specific sense. It was invented in the late 20th century as a mass produceable, attractive way to teach school children origami. To a serious folder it is usually not used in a finished model; it is prone to fading, may be too thick or thin, may be inaccurately cut and generally leads to an unimpressive result. However, it is in wide use since it is cheap - often selling in packs of a hundred or more and comes in a dazzling range of colours.
A sometimes more suitable and certainly traditional paper is washi, or chiyogami if it is patterned. Washi is not made from wood pulp like office paper, instead it is made from a plant fibre called gampi. It can also be made from mulberry, wheat or rice. As such, it is quite soft and has a fluffy texture. It is often patterned with bright colours and shapes such as birds, flowers and geometric shapes. Washi is good for simple models but with complex creasing goes mushy and tears.
For complex folding, such as the many legged insects of Robert Lang foil paper is a good choice. Foil may be adhered to paper or even tissue. The foil provides stong creases while the paper stops rippage.
For wetfolding - origami with damp paper that dries into curved shapes - paper with a substance called sizing is used. This substance when damp releases the paper fibre and when dry locks it in place again. A suitable paper for this is watercolour paper, which is quite thick and can absorb a lot of water.
Other specialty paper includes tant, which is relatively thin and strong, and handmade paper, such as the kind from the Origamido studio which is made for specific projects.
All that said, to start learning origami no special paper is needed. Origami can be made from office paper, tissues and lolly wrappers. Even things that aren't paper, such as banknotes, napkins, sheet metal and plastic film have origami potential.