How do apps recognize you after you delete them?
Developer access to the UDID was removed in iOS 6, so they are not (no longer?) using that.

The replacement was identifierForVendor. However, once the last app by a particular vendor is removed from a device, even if an app from that vendor is re-downloaded in the future, the identifierForVendor will change. So that's out too.

Given that a factory reset of a device will cause the link to break (according to various reports on the internet), the best guess is that SuperCell, or whomever, is using the advertisingIdentifier. This uniquely identifies the user, regardless of app vendor, and survives deletion of apps. The only time it changes is, you guessed it, during a factory reset.