I don't know of any Android Market API that will tell you if the user downloaded/used the app before.
I think that you'll have to do it yourself which gives you two choices to persist data across an app uninstall/reinstall cycle:
(1) save a file on the SD card an check that to see if the app was installed before or
(2) contact a server with some user specific info to check if it was downloaded/used before.
The problem with the SD card method is that its not effective if the user erases the file or switches SD cards.
For the server model, you'll need to have a server to record some piece of information like user id or device id or some mix.