I used to use the litter genie but sometimes I'd wind up with not enough plastic to tie at the end of the roll, so I thought that was a bit wasteful. So, I switched to compostable bags (green):
Compostable Trash Bags, 2.6 Gallon Food Scrap Yard Waste Bags, 100 Count, Extra Thick 0.71 Mil.

The one drawback to these is that they're kind of flimsy so they don't stay open for you. But you can invert them and cover your hand and pick up stuff with them (quickly).
Once a week I'd empty out the litter box. I also used newspaper-based litter but my favorite was the grass seed type. I used to use sWheatscoop but it had bugs in it once and that turned me off. I think my cat was allergic to grass seed so that's why I switched to newsprint (Purina discontinued my favorite type of that so I had to make do with another). I don't like clay litters (how they smell and how they track all over).

My cat died yesterday so any cat talk is making me feel a bit better right now.