Seems to me the pretty easy solution is for grocery stores to start charging for plastic bags. Even a nominal charge will get customers to be far more likely to bring their own. Like, if you charge 10-20 cents for plastic bags (and say, 1-2 dollars for cloth bags. Adjust these figures as you will, I haven't thought either through), it does not meaningfully impact the price of groceries but people will notice and be more likely to bring their own.
Economic incentives, people. They work.