Using an Arduino Nano, how many LEDs can I safely power?
If you are running the LEDs from shift registers then the power rating of the Nano is irrelevant.

If you are wanting to use the Nano as the power source (not recommended) then you would need to know both your expected current and what the regulator on the Nano would be able to supply.  My immediate guess is "not enough".

64 LEDs at full brightness would be expected to use a maximum of say 20mA each, so 1.28A just for the LEDs.  That's a huge amount, and way more than any linear regulator can be expected to supply without melting everything around it.

So you can reduce your current requirements by not having the LEDs as bright.  Half the current does not equate to half the apparent brightness. In fact at half the current you probably won't notice much difference at all.  At a tenth of the current you will see them a bit dimmer, but not as much as you would expect.

So you can come up with a compromise between the brightness you desire and the current consumed by each LED.  

Say you end up deciding on (as Gerben has suggested) a current of 5mA per LED.  When all LEDs are on that would be (5 × 64) 320mA.  That's reasonable for a linear regulator, but still will generate more heat than is really advisable.

So you should, for this project (assuming you aren't going to be using multiplexing, which is a whole other ballgame), investigate using a switching (aka "buck") regulator.  You can pick these up on eBay for just a couple of dollars and can quite happily supply amps as opposed to milliamps and will allow you to run far more LEDs without going into thermonuclear meltdown.

Another important consideration to think about is how much current an individual shift register can provide - both through its output pins and in total for the whole chip.  There are special constant current LED driving shift registers that remove the need for individual resistors on each LED and give much better control over the LEDs than traditional logic output shift registers.