We investigate the laser-induced ultrafast injection of spin from a ferromagnetic (FM) material into a nonmagnetic (NM) one, for a diverse set of FM-NM interfaces. For all systems, we find the early time (t < 20 fs) spin dynamics to be driven by spin currents, with majority spin transferred to the NM and minority spin to the FM. At later times, spin-orbit-induced spin flips further demagnetize the FM, but also deplete the NM of the substantial spin moment injected during the sub-20-fs spin dynamics. We identify the density of unoccupied states in the NM material to be the key physical property that underpins the physics of ultrafast demagnetization of FM layers and a complex interplay of this density of states with the spin-orbit (SO) coupling strength of the NM substrate to be responsible for spin-injection efficiency.