I just noticed all the customers who use paypal express checkout are unsubcribed to the newsletter by default.

Is there anyway they can choose whether or not to subscribe when using paypal express checkout?
GoogleCheckout does offer this option and most customers do subscribe when given the option to choose.