Actually don't. Paper bags are MUCH worse for the environment than plastic. Paper bags are not just an example of a waste of effort, but actually have negative value! (Reusable is good of course, and on that note plastic is much easier to reuse as a trash bag than paper, but even if you don't, plastic is better.)
There is all the energy AKA oil used to make them. From driving the machinery used to cut the tree, then transport the tree, mill it, process it, bleach, then color it, then you have to dry it (heat), and finally transport it. And paper is big and bulky and uses a lot more energy than plastic does to do all that.
Then you have the real problem: water. It takes a lot of water to make paper, and there is a MUCH bigger shortage of water compared to oil.
But even if you want to look at oil alone, paper bags use more oil than plastic ones do.
Some numbers I posted: http://news.ycombinator.com/item?id=965694
Paper uses more than 4 times as much energy as plastic. And releases much more pollution, and more water, and takes 85 times as much energy to recycle.
It looses in every way except litter.