Yes, the C3PO you see pictures above is indeed made entirely of paper. As one not well acquainted with the art of papercraft, I'm nothing short of amazed by it. It's an incredible design. The good news: if you've got the patience to assemble it, you can easily build your own. The design is available for free in PDF form.
The bad news: it's incredibly complex, and the instructions are in Japanese. Then again, there's never been a better time to take up a new language.