Melting ice with salt - how does it start?
I believe that Ivan's comments are on the right track. Generally any melting phenomenon to do with ice begins with the fact that the surface of ice is disordered. By this I mean that ice on the whole is a periodic crystal like other solids, but at the surface there are imperfections, primarily due to the extra conformational freedom afforded to the surface molecules. This distortion then propagates down quite a few layers [1]. Ref. [1] discusses the properties of this surface layer which is liquid-like, and points out that this layer exists even down to quite low temperatures.

If these surface molecules "see" something charged (each ion that is) like $\ce{NaCl}$, then the surface molecules already have the conformational freedom to solvate the ions. Additionally, there is an energetic benefit to this because the hydrogen bonds between these ions and water are stronger than the water-water hydrogen bonds.

In general, melting phenomena are extremely complicated and the question of how melting "begins" is has not really been answered completely or satisfactorily (can provide refs. later if you want). This case is a bit different though because it is really a solvation phenomenon, which is adequately explained by the liquid-like layer at the surface.



[1]: Beaglehole, D., &amp; Nason, D. (1980). Transition layer on the surface on ice. Surface science, 96(1-3), 357-363.