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 smaller than 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.