How does the device knows an app is installed before?
Applications might use techniques, such as hidden files, benign modifications to other files ... some have even been known to write to hidden parts of your hard disk.

So basically when you install the program it probably writes a hidden file or entry in your phone to "mark" that phone and let it know that you've already done the trial period.  It also probably keeps track of your e-mail address that is linked to your google play account or itunes store account, maybe even keeps track of your phone's id(depending on how deep these programs go.)