As one could imagine, there is a considerable amount of conjecture as to precisely Earth got its salt content. Ultimately, it came from the primordial planetary nebula and concentrations of the ions involved would have come from the various ingredients of the accretionary process. This answer focuses on how salt may have first formed, hence accumulated.
Ocean salinity is almost a chicken and egg situation - was their salt before the first waters or vice versa? According to current research, the latter appears to be true, especially in the case of the dominant $\ce{NaCl}$ species.
Knauth (2005) (2) contends that $\ce{Cl-}$ ions were outgassed through volcanic eruptions in the form of $\ce{HCl}$ and $\ce{Na+}$ were theorised to have been leached out of rocks (1). The exact amount of these ions and salt content are not entirely known (3), but the process may have started even as far back as the Hadean, and certainly in the Archean (3) and the early water bodies were believed to have been up to twice as saline as today (2).
In terms of halite deposits, this requires evaporation of a brine, which according to Knauth (2005) (2) and Sleep (2010) (3) required large enough continental masses to be able to enclose water bodies - the amount of this occurring in conjectural for Earth, as the halite produced would be unlikely to be preserved (3).
Knauth (2005) (2) expanded on the implications of this for other worlds with:
Inasmuch as chlorine is a common element throughout the galaxy and follows the water during atmospheric outgassing, it is likely that early oceans on other worlds are also probably so saline that evolution beyond the microbial stage is inhibited unless long-lived continental cratons develop.
Partly suggesting that the formation of salt is possible on any world - such as the salt found in Martian sediments, as per the article Magnesium sulphate salts and the history of water on Mars (Vaniman et al. 2004).
References
(1) Einsele, G. 1992 Sedimentary Basins: Evolution, Facies, and Sediment Budget (Book)
(2) Knauth, L.P. 2005 Temperature and salinity history of the Precambrian ocean: implications for the course of microbial evolution Palaeogeography, Palaeoclimatology, Palaeoecology
(3) Sleep, N. 2010, The Hadean-Archaean Environment Cold Spring Harbor Perspectives in Biology