Lots and lots and lots of paper chains
.
Or you could papier mache (sp?) some things. I think papier mache is what I'm on about. Where you tear strips of paper up and layer it on with pva glue. It dries hard and shiney. You could make baubles for the tree (inflate a balloon a little bit, cover it in paer and glue and when dry pop the balloon with a pin).
Or buy blanks from a craft shop and cover them.
Did I mention paper chains?