How to prevent NFC tag cloning?

That depends on what type of tag you use and what level of protection against cloning you want.

1. NFC tags (as defined by the NFC Forum) have no protection against cloning. Such tags are intended as containers for freely readable data (so called NDEF messages). Anyone could read an NDEF message from one tag and duplicate it to another tag.

2. Many NFC tags also contain a unique identifier that is pre-programmed by the tag manufacturer and cannot be modified on normal tags. You could use this unique identifier to determine if a tag was issued by you (i.e. you know its id) or forged (i.e. you don't know its id). Instead of using a list of genuine ids, you could also create a digital signature over the tag's id and its data. THat way, you could find out if data and signature are used on a tag with a different unique identifier. However, all data can still be extracted from your tag. Therefore, you should be aware of the fact, that specialized hardware (e.g. Proxmark, etc) and ready-made tags are available where an attacker can change the unique identifier to the value of your tag's id. So this is certainly not perfect cloning protection.

3. You could use a contactless smartcard/tag that provides communication encryption and shared-key based access control (e.g. MIFARE DESFire). With this approach, you could store data that you do not want an attacker to be able to clone in a key-protected memory area. However, if you want to be able to read that data from within your app (i.e. without having an online backend that directly communicates with the card), you would need to store the key to access the memory area within your app. Consequently, in an offline scenario (i.e. key stored in app), an attacker might be able to extract that key and use it to clone the tag.

4. You could use a tag/smartcard that contains a secret asymmetric key and provides a command to sign a cryptographic challenge with that key. In that case, in order to verify if the tag is genuine, you could request such a signature from the tag for a random challenge and verify the signature against the tags corresponding public key. This would certainly be the most secure solution as you do not need to store any shared secret within your app. The only ready-made NFC tag solution (that I'm currently aware of) that provides such functionality seems to be Inside Secure's VaultIC. Though you could create one yourself based on the asymmetric crypto functionality of a contactless smartcard (e.g. a Java Card).

Note that for all of the above cloning-protection scenarios you would have to create an app that checks if a tag is genuine or cloned. By default NFC phones only use the information in (1) and therefore do not perform any such checks.

Yes it's possible meanwhile to prevent cloning a Tag.

There is a new tag called the NTAG 413 - which can generate a new NDEF message every single time you tap it. (using AES krypto) This way it's not necessary to have a seperate app installed on your smartphone. You can incorporate the encryption in the URL of a NDEF for example and the host server can encrypt it with the same key. In case of copy the server will recognize it.

Some companies already offer them in different form factors, for key cards (hotels or access). More info can be found in this link but it's german..

https://www.variuscard.com/plastikkarten/chipkarten/nfc-ntag-413-dna/

While the original answer was correct it's getting a little bit out of date. Michael's addition (Oct 10, 17) added the NTAG413. There's now another additional NTAG424 DNA authentication NFC chip, which works in the same way. HID's Trusted Tag works in a similar way and there increasingly others.

Essentially the chips create a new unique code based on a stored key on each tap/scan. Code can be verified from a server.