How do they know if the customer is new or not?

tracking via cookies (that expire after X days) or some kind of identifier in the CRM

Normally in e-commerce, it's based on email or phone number. In physical retail, they use all sorts of tactics, from loyalty cards to facial recognition (where legal, which it shouldn't be).