LED Battleship project

Hi Everyone..
I'm new in Arduino world. I have a bit of electronic knowledge and I have an idea of doing a battleship game with my son.
Project will include a 4 boards of 8x8 led (256 in total). LEDs will be controled by few buttons (to set up a position of the ships, mark them, and reset - so I think 12 all together). Biggest challenge for me is to find out whats the best solution to control that many leds. Maximum number of leds on in a same time will be 80. I think that might be to much for my arduino uno r3.
I thought about using shift registers to control leds, but i dont really know if thats gonna work.
Is it better to split all of that set up for 2 arduino's? I have tried to find similar things already.
Cant find anything good with a manual how to control that many leds with push buttons..

Does anyone have an idea how I can do this project?
Thanks.

So far the best one I have found was:
http://vimeo.com/64255717
but I would like to use normal leds instead of dot matrix ones.

but I would like to use normal leds instead of dot matrix ones.

Why?

You could do it simply with a MAX7219 per matrix.
http://playground.arduino.cc/Main/MAX72XXHardware

groundfungus:
Why?

Becouse I would like to build a bigger version of the game…

Grumpy_Mike:
You could do it simply with a MAX7219 per matrix.
http://playground.arduino.cc/Main/MAX72XXHardware

UUU ok… I’ll try that… Thanks…

Then maybe look into LED strings. Some have built in controllers (ws2812). To match the project in the video will require wiring a couple thousand discreet LEDs.