Oddly enough, there's actually a "correct" answer to this dilemma that hasn't been mentioned yet. (Don't worry: /me to the rescue!)
Besides the obvious answer (reusable, canvas shopping bags that are widely available for about $5 or $6 each), it's clear that paper bags are FAR superior to plastic bags when it comes to the environment.
Even though they both end up in trash dumps and both take forever and a day to biodegrade, one simple fact remains:
Paper is a renewable resource. Plastic is not.
Though we're certainly using more paper than we should (and recycling less than we should), it's still preferable to use a renewable resource than a nonrenewable one. Because while we can always plant more trees, our petroleum reserves are quite limited.
So, in short, take advantage of reusable, washable, hippie-friendly canvas bags when you can. (Buy a couple, throw them in the trunk of your car, and then you'll never be without.) But if you're in a pinch, paper is definitely the more-eco-friendly way to go when compared to plastic.
machfive points out: Some stores will give a 5 cent credit for each canvas bag you use. So if you fill up 5 bags with groceries every week, that's a quarter. At the end of the year, you've saved $13.00! Oh, and don't forget paper bags can be recycled as well. Throw your newpapers into them, and take them to a recycling center!