So I solved it by moving my redirect to a separate method:
def redirect_to_paypal_preapproval(key)
redirect_to URI.encode("#{Rails.configuration.paypal.preapproval_link}#{key}")
end
Then in my cucumber test I put:
PaymentMethodsController.stub(:redirect_to_paypal_preapproval)
.and_return(visit payment_methods_path)
That seemed to redirect on it's own back to my app as if the approval was a success