Simply get their PayPal info and send it, its as simple as that. I rarely use PayPal anymore other than for just small stuff or if its someone who just refuses to deal any other way besides PayPal.
If they request you to send it as a gift (so they don't have to pay the fee) I suggest that you don't do it. You have no way to recover your money if you get ripped off.