YAY for your first eggs! I'd avoid hay-- but that's just because I have read the "crop surgery" on all the hens that eat hay and it gets stuck in their crop. Pine shavings seem to be fine. You can line the bottom of your nest with the rubber shelf liner first and then throw your shavings in. A cat litter box with a top will work great, too.