NDEF "formatted" means that a tag is capable of holding a NDEF message. This means that
for tags with flat memory structure (e.g. NFC Forum Type 1 and Type 2 tags), certain pages are filled with defined values (e.g. the "capability container") that let an NFC device determine that the tag adheres to a certain version of the Tag Operation specification and that it contains a defined amount of NDEF formatted data in a defined memory area.
for tags with a file-system based memory structure (e.g. NFC Forum Type 3 and Type 4 tags), a certain file and directory structure exists on the tag and meta information (e.g. contained in a capability container file with a well-known file ID for Type 4 tags) indicates the location, size and other parameters that allow an NFC device to access the NDEF formatted data.
For standard NFC tags, this formatting (and the commands necessary to interact with the tags) are defined by the NFC Forum in the Tag Operation specifications (get them from the NFC Forum website). In addition some manufacturers like NXP have defined mapping documents that describe how to use their proprietary RFID tags (i.e. non-NFC Forum tag types) such as MIFARE Classic to store NDEF data. These mapping documents describe the data structures that need to be present on a tag to be identified as container for an NDEF message.