What is the best way for controlling array of 8-16 relays?

Using Arduino Project Guidance
8
  1. If relays are powered from external power supply, should the grounds be connected?

definately, thats the common reference for both the logic and the driver parts of the chip.

  1. Where to put capacitor and why it is needed?

You will always need a 100nF capacitor near to any chip, between the 5v and ground for decoupling, and you will also need a 1000 MFd electrolytic close to the relays 12v supply, to smooth any surges as the relays open and close .

  1. May I use arbitrary pins for data/latch/clock?

If you are using shiftout to switch the relays then you can choose the pins. ( shiftout is easily fast enough for switching relays )

  1. What will be the state of output pins on power on/restart?

You can set up the state of the all the pins during start- up. ( or there is a simple way to store the states in eeprom at power-down, to reload at power up again )