I did it this way:-
1. Found out who's responsible for purchases in that specific store.
2. Find out when they might be available
3. Make the first visit just a short one and leave a sample
4. On the next visit, take a few prices of how much a product would sell for
5. Give them a few samples to see how it would sell, be confident and show them why its worth it.
6. Visit the store after a few days or so, help them with any material they need, posters etc.. if the product don't sell, you won't get a re-order.
The above approach made it possible for me to win confidence with the 5+ big stores where I have my products. It's also made the stores realize that I will go all the way to make sure my product is what it says it is and I usually throw in an hour or two to present the product to their customers on the first weekend of the product.