Here's how REST API billing plans and billing agreements work (including curl call samples):
First of all, please make sure that your REST app is toggled for subscriptions (You can check your REST app settings on https://developer.paypal.com/webapps/developer/applications/myapps )
1-) Create Billing Plan
curl -k -v -H "Content-Type:application/json" -H "Authorization: Bearer ACCESS_TOKEN" -d '{"name":"Test REST Club Plan","description":"Template creation.","type":"fixed","payment_definitions":[{"name":"Regular Payments","type":"REGULAR","frequency":"MONTH","frequency_interval":"2","amount":{"value":"100","currency":"USD"},"cycles":"12","charge_models":[{"type":"SHIPPING","amount":{"value":"10","currency":"USD"}},{"type":"TAX","amount":{"value":"12","currency":"USD"}}]}],"merchant_preferences":{"setup_fee":{"value":"1","currency":"USD"},"return_url":"http://returnurl","cancel_url":"http://cancelurl","auto_bill_amount":"YES","initial_fail_amount_action":"CONTINUE","max_fail_attempts":"0"}}' https://api.sandbox.paypal.com/v1/payments/billing-plans
PayPal will return a billing plan ID starting with "P-"
2-) Activate Billing Plan
curl -k -v -H "Content-Type:application/json" -H "Authorization: Bearer ACCESS_TOKEN" -d '[{"path":"/","value":{"state":"ACTIVE"},"op":"replace"}]' https://api.sandbox.paypal.com/v1/payments/billing-plans/
3-) Create Billing Agreement
curl -k -v -H "Content-Type:application/json" -H "Authorization: Bearer ACCESS_TOKEN" -d '{"name":"Test REST Club Plan","description":"Template creation.","start_date":"2015-03-20T07:49:27-07:00","plan":{"id":"PLAN_ID_HERE"},"payer":{"payment_method":"paypal"},"shipping_address":{"line1":"111 First Street","city":"Saratoga","state":"CA","postal_code":"95070","country_code":"US"}}' https://api.sandbox.paypal.com/v1/payments/billing-agreements
PayPal will return an Express Checkout re-direct URL with a EC token. E.g. https://www.sandbox.paypal.com/cgi-bin/webscr?cmd=_express-checkout&token=EC-xxxxxxxxxxxxxxxxx
You need to re-direct your customer to PayPal via that URL. Once the billing agreement is authorized, customer is returned to your site (return_url in step 1).
4-) Execute Billing Agreement
curl -k -v -H "Content-Type:application/json" -H "Authorization: Bearer ACCESS_TOKEN" -d '{}' https://api.sandbox.paypal.com/v1/payments/billing-agreements/EC-TOKEN_HERE/agreement-execute