It's ideal to recruit an opposite gender NPC very early. Get a weapon or summon something, win a few battles, and your reputation goes up. You need rep level 1 (and no clue how to properly describe it or even say where you find it) to marry. It's something that can happen very early, then you can get those kiddies squeezed out, it takes them a while to grow up to be useful.
To marry an NPC you don't have to be anywhere near them. Just park them in your capital and when you're ready to marry, just select them, go to actions for them, and look for the golden ring icon (propose). Babies soon follow. Check out your dynasty under kindom info, the babies in cribs are soooo cute. 
