The plastic deformation of metal alloys localizes in the Portevin-Le Chatelier effect in bands of different types, including propagating, or type "A" bands, usually characterized by their width and a typical propagation velocity. This plastic instability arises from collective dynamics of dislocations interacting with mobile solute atoms, but the resulting sensitivity to the strain rate lacks fundamental understanding. Here, we show, by using high-resolution imaging in tensile deformation experiments of an aluminum alloy, that the band velocities exhibit large fluctuations. Each band produces a velocity signal reminiscent of crackling noise bursts observed in numerous driven avalanching systems from propagating cracks in fracture to the Barkhausen effect in ferromagnets. The statistical features of these velocity bursts including their average shapes and size distributions obey predictions of a simple mean-field model of critical avalanche dynamics. Our results thus reveal a previously unknown paradigm of criticality in the localization of deformation.