Where I live there's a small fee per bag if plastic, free if paper (and the store offers it), or you bring your own. It's virtually eliminated plastic bags at stores and also had the side effect of eliminating them as a second-use source for small bags around our household -- e.g. organic trash, small bins, etc. We never tossed these bags as-is, they always had a secondary function.

As our previous inventory shrinks (we had collected around a hundred of them), we've started introducing more of the large plastic vegetable bags from the grocery and/or considering just buying a box of a thousand grocery store bags from Costco as their form-factor is really useful (easy to tie-off to help control smells).