Bom, tu vai precisar de 15 74HC595 + 15 ULN2803. Usando a função shiftout do arduino.
http://arduino.cc/playground/Portugues/LearningShiftOut
Mas o número de ULN2803 pode ter que aumentar um pouco que o máximo de corrente suportada pelo chip é de 500mA
Então você precisa achar relês com corrente de acionamento da bobina de no máximo de 60mA ou utilizar 20 ULN2003 usando de cada chip apenas 5 entradas/saídas de cada um, ai pode usar relês com bobina de 100mA.
E claro que provavelmente uma fonte de 11~12A para quando houver acionamento de todos os relês se consumirem algo em torno de 100mA simultaneamente.