Velocity statistics is a direct probe of the dynamics of interstellar turbulence. Its observational measurements are very challenging due to the convolution between density and velocity and projection effects. We introduce the projected velocity structure function, which can be generally applied to statistical studies of both sub- and super-sonic turbulence in different interstellar phases. It recovers the turbulent velocity spectrum from the projected velocity field in different regimes, and when the thickness of a cloud is less than the driving scale of turbulence, it can also be used to determine the cloud thickness and the turbulence driving scale. By applying it to the existing core velocity dispersion measurements of the Taurus cloud, we find a transition from the Kolmogorov to the Burgers scaling of turbulent velocities with decreasing length scales, corresponding to the large-scale solenoidal motions and small-scale compressive motions, respectively. The latter occupy a small fraction of the volume and can be selectively sampled by clusters of cores with the typical cluster size indicated by the transition scale.