NYC-AUS is serviced nonstop by B6, UA, DL and AA. B6 doesn't transport animals as cargo and your 35lb pooch is over their cabin limit. The dog will be over the cabin limit for all of those airlines. But you'll want to see which has the best schedule for you and the fees associated. I think they generally range form $100-$150 USD.

You can't pay with points (converted to miles) for the pet fee but you can use the points towards the flight and/or use the points to pay for the fee as credit against your statement balance. Or if your Amex or Chase card offer a travel credit the pet fee can be applied to that. For example the Amex PRG has a $100 annual airline fee reimbursement.

FT has a traveling with pets forum that may provide you with more info.