In Germany, single use plastic bags have not been allowed in supermarkets for several years now and it has worked quite well IMO.
Yes you can buy thicker re-usable bags (sometimes made out of textiles or a mixture of textiles and plastic) but by far many people bring their own bags, or just load the stuff into shopping trollies and take it to their cars (unfortunately the petrol/diesel car culture is still going strong :( ).
Also, in places like Lidl and Aldi, it's quite normal to just look for an empty box of some product on the shelf(e.g. a box that had some canned goods) and use that as your 'basket', stuff your items there, pay, go home and dispose of the box in the paper recycle bin.
EDIT: I also forgot to mention, as an example of culture/attitude: plastic bags are still available for fruit & vegetables but even then, people do make their own choice to just take the produce without a bag, and place it 'loose' at the cashier for them to weigh.