Hebbian theory "fire together" clarification
Strictly stated, Hebb's rule applies only to existing synapses, and not to the formation of new synapses. (This answer applies to biological neurons, not to ANNs).

Synapse formation is a topic of active research. During development (and in fact continuously even during adulthood), many synapses are created and destroyed. It is not unreasonable to suspect that a similar form of rule is used to decide which synapses are removed and which should remain.

Synaptic connections between neurons show a good deal of specificity -- for example, in the projection from the retina to the optic tectum, synaptic connections are made only with target neurons at an appropriate retinotopic location. This happens because growing axons follow molecular gradients.

Within a cortical column, some possible connection pathways seem to be actively sought -- for example, axo-axonal cells connect specifically to the axon initial segments of target neurons. Neurons certainly have membrane molecules that could be used to identify target cell classes.

So there are probably a number of rules used to determine when a new synapse is made. However, I am not aware of a mechanism for a pre-synaptic neuron to detect how a putative post-synaptic parter is firing, without a synapse already being present. So it seems likely that some form of random process is involved to form new synapses with reasonable post-synaptic partners, after which some activity-dependent rule (like Hebb's) could be applied.