Well, just in case anyone else looks for sawdust or shredded newspaper and finds this thread and this post, the shredded newspaper does fine as bedding and they WILL lay eggs in a nesting box with shredded newspaper in it. Also, the sawdust is BRILLIANT for spreading on the floor to absorb waste products. I also put shredded (run through the shredder) cardstock in a nesting box and they REALLY like that. We have had a lot of eggs layed in that box.
As far as the newspaper goes, I found that the smaller I ripped it up, the better they liked it.