How exactly does "CoinDance" determine the current number of public Bitcoin nodes?
Does the Bitcoin network send around an integer saying how many nodes there are to each other as part of the protocol,

No.
See https://en.bitcoin.it/wiki/Protocol_documentation
So far as I can see, total counts of active nodes are not part of any message but there are potentially useful messages such as:

getaddr
The getaddr message sends a request to a node asking for information about known active peers to help with finding potential nodes in the network.

By sending this message to all known but previously uncontacted nodes, it is possible to discover more previously uncontacted nodes you can send this message to until the responses only contain previously contacted nodes and all the nodes you know of are either contacted nodes or unresponsive nodes.


I'd like to know how exactly they determine this,

CoinDance don't say.

As Davidson Souza's later answer reports, at least one website (Bitnodes) uses the getaddr message to approximate the number of all currently accessible nodes.