I think that anyone who is proficient in English grammar will search for a store properly, i.e. Sam's Store, versus Sams Store. However, that presumes that the store owner is also proficient in English grammar and actually did up the store name correctly!
I think a lot of people would search both ways, once for "Sam's" and again for "Sams".
Those who wonder about such things could put a wildcard (*) at the end of Sam, i.e. Sam*, and that way all results that start with SAM would appear. Of course, that might result in a lot of names other than Sam's and Sams, like Sambini, Samboni, etc.
I used the apostrophe in my eBay store name, but the url for it excludes the apostrophe. When you search eBay stores, however, my store shows up only when the apostrophe is used. I did a quick store search for all the stores that have my first name. Three times as many have the apostrophe compared to the number that do not use it.
Happy sales!