I'm not too surprised that an online gun store got hit. I'm sure that a hacker could sell the names/addresses of gun owners to criminals who would like to know who to steal guns from (sure is a lot easier than following people home from a gun shop). If they also got what product was purchased, it could quite literally become a shopping list for criminals.
I wouldn't discount a notice by mail - was it registered mail where they were trying to have proof that they notified you? Obviously if the letter is saying "call us and give your name, address, SSN, DOB, and credit card numbers to see if you're a victim of identity theft" it may be a scam, but if it's just a notice that says "on x day we found that we had suffered a data breach, please keep an eye on your accounts" I think it would be more likely to be real.
If in doubt, call the company (google their phone number, don't use the phone number on the suspect document) and ask if it's real.
