How do some android apps remember that this is not the first time they are being installed? Some android apps are can remember whether they were installed on the same device earlier. Suppose you uninstalled an app a year ago. After one year if you install that same app again, that app will be able to recognize that it was installed before on the same phone.

This technique is used by online applications to permanently ban users from ever creating a new account again if they have been banned from using the service once. When such users create a new account by reinstalling the application later, these apps are able to detect their "first time presence" and send this information to servers so that user can be banned again.

How they do it even after clearing their data and uninstalling them completely? It means they keep some file somewhere in the phone, which is not deleted after uninstall. How do I disable this detection?
There are multiple ways to identify a unique device or its user:


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).  
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.  
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.  
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.