Means they are not an authorized dealer and got the watch from another distribution source other than the manufacturer. There usually is not a manufacturer warranty and may not have papers. They may offer your their own warranty.
The upside is that they aren't held to the price minimum that manufacturers may have. Gray market dealers doesn't mean shady, although there are some. Costco is a known gray market dealer when it comes to many luxury brand goods they carry.
Gypsy, here is a nice chart that categorizes watches. My good watch is Ebel which is in the luxury category right there with Cartier. The difference is, I was able to get the Ebel I love brand new with a discount for around the cost of the Tank used. Hard choice but diamond bezel did it for me! I like quartz for everyday. Don't feel bad. (And Longines comes in some great styles and is fine for an everyday watch...I have two but I got them half price!).