If I was to power an Arduino Nano v3 with 12volts into the VIN pin, and run a servo capable of handing 5 volts from the 5v pin on the arduino, would that work? An example would be the standard Sweep tutorial, would one 12v battery power the arduino and the servo without frying anything?
The on-board 5V regulator most probably is too weak for powering a servo. Such an attempt should not damage anything, but the regulator will shut down on over-current or over-heat, and the controller will reboot all the time.
Depending on the servo current, you should at least use a power supply of about 7V, to reduce the heating of the regulators, and add an 7805 regulator (with heat sink?) for powering the servo. Or you get a reliable(!) 5V supply, to power both the controller and servo.