I've used newspaper, copy paper, brown paper sacks, you name it. Some use cigarette paper. No real need to nitrate the paper unless you just want to.
I use a kids glue stick to glue the paper and glue the bullet to the paper. Lots of good info on cartridge making over at the shiloh rifle forums in the 1863 support forum.
Quick and dirty cartridges can be rolled with a tail that gets cut off when you close the breech. Guys shooting for best accuracy (and the guns are suprisingly accurate) make a cartridge that loads flush with the breech and seal the end with curler paper (available where beauty supplies are sold. A coupla bux will buy thousands of 'em) just as you would do with Charlie's tubes.
Dunk the bullet end in molten lube and you're ready to go.