First you have to recruit a champion of the opposite sex. When you click on that champion and go to their available actions, you'll see an icon of a wedding ring. Click it. One of two things will happen. She'll marry you, or she'll say your reputation needs to increase and then she'll marry you. I think it's nice then you never seem to get a flat "No" or "Ugh...no".
