Blinkenlights with Arduino

Hy,
I have a question about extending Arduino and equiping it with 64 Outputs.
What do i want to do:
controlling 64 light Bulbs in an 8x8 Matrix to build a hughe screen like in the Blinkenlights Project you can see here:

http://vimeo.com/6175054

The Problem:
I need 64 Outputs with 5V each to controll 220V AC Relais. This might be done by shift registers or multiplexing with an adress BUS. Does anyone have some experience by doing this?
I recently built a 64 RGB Matrix what was quiet easy but therefore i had tools like this one:

http://iteadstudio.com/store/index.php?main_page=product_info&products_id=312

And I’m not quiet sure if this might be suitable to control 64 Relais :-S

Thanks a lot and help would be highly appreciated :wink:
Greetz
Andi