I am unsure of your grade level. They could type or you could type them on computer and print on pretty Christmas paper. You could have them write it on the lined paper and cut and paste to pretty Christmas computer paper. You could use have them write it on the lined paper and glue it to sturdy wrapping paper or Christmas bags (cut to fit, of course).
All of this also depends on the grade level and length of the stories. If it is lengthy, you could have them fold card stock paper in half and put pages inside and decorate the cover. I have special paper for publishing stories such as the author page, title page, etc. Someone gave me mine some years ago. The children love them. They can use them to publish their story anyway using construction paper, card stock, wrapping paper, wallpaper, border, shelving paper, old greeting card covers, etc.
Hope all this makes sense and helps you....
I have my students publish their holiday stories (eg, the best gift I ever got, etc) and then sandwich the paper between two sheets of construction paper. They decorate the front piece as a package with ribbon and a bow, and we add a tag for their name. These look so cut hanging in the hallway!