s“Sac de magasin” would be grammatically correct French, but it would mean a bag which is generically associated with stores (it could be a kind of bag that is made by stores, or a kind of bag for use in stores, or some other association, similar to “store bag” in English). The expression “sac de magasin” is not commonly used for anything in French. If you brought your own bags to use in shops, they could be called “sacs de magasin” if we ever used this expression in French. Grammatically, here, “de” is the preposition de (“of”) plus a partitive article.
“Sac du magasin” means a bag of “the” store. In context, “the” refers to the store that you're in. In this context, it clearly means a bag provided by the store. The association between the bags and the store could be different, for example it could mean a bag decorated with the store's brand, although in practice those would be provided by the store anyway. Grammatically, “du” is the preposition de (“of”) plus a definite article (in masculine singular form).