Android - How do some android apps remember that this is not the first time they are being installed?

There are multiple ways to identify a unique device or its user:

1. Keep a file in some (non-default) directory: You already said this; apps can often write to the internal storage of a device. This method is easy, works offline and is not the easiest to spot (place the file in some system-like directory and nobody will bother deleting it).
2. Keep track of a devices unique ANDROID_ID (unique per fresh installation): this method is simple but requires internet access, at least on the first use. It's not very intrusive and does not persist in case of a factory reset. It's also unique per user. See this information.
3. IMEI: Very intrusive, unchangeable but requires a SIM-capable device. The IMEI is unique for each device, cannot be changed and doesn't follow the user, meaning that if you sell your device, the new owner will be greeted with a screen telling him that the app was already on the phone.
4. Follow a user's Google account: This is pretty much the same as the ANDROID_ID approach but requires explicit permission (Android 6.0+) from the user to access. Apps that take advantage of the Google account ecosystem (e.g. highscores and achievements in games) can thus follow a specific user and gain more information than just whether the app has been installed or not.

2, 3 and 4 require a network connection and a server on the side of the developer.

It is not connected to storage, but to the cloud. That is how it remembers even though you deleted your data. In order to switch this off, go to your device's settings app, tap accounts google under personal (tap account you want if you have multiple accounts), then switch off the apps you don't want to auto-sync.

GiantTree's answer covers it best, but there is another point to think about. It would clearly be a "dark pattern" but this identification could also be done through fingerprinting certain user data - this can be viewed as a variant on his first point ("keep a file") but it would be harder to detect and less convenient to avoid.

How resilient this is would depend on the data chosen. The most obvious method would be looking at contact details and using some form of fingerprint of this; an alternative might be use of photo timestamps and other metadata. Clearly these change over time so whatever method was used would need to still give a close answer after modification (so it differs from a traditional hash function). Also there is no guarantee that a user doesn't simply wipe the tracked data, but in many cases people will prefer not to do this.

You may wish to look at browser fingerprinting to get a sense of how this works, even though it is going to be somewhat different because phone hardware is typically more uniform than PC hardware. That said, the addition of certain phone details may help narrow the fingerprint down a bit.

Where this approach breaks down in particular is if a user switches phones and takes their details with them to a new phone - in this case (unless phone details are going into the fingerprint) the new phone might be detected as already having had an installation, as the question asked. However it seems quite likely that in a scenario where an app is trying to ban a user, this might actually be a desired outcome (rather than banning the specific phone itself)

Please note: In no way am I saying this is correct or "good" as a way to operate if you're writing apps, but it seems reasonable to discuss it as it is only through discussion that people will figure out whether they're concerned enough to do something about it and what that might be.