You can use shift registers to control the relays. This will only use 3 pins and allow you to use the xbee.
For the RGB LEDs you can use the TLC5940 to control 16 channels, so you will need two, giving you 32 channels. This is a PWM chip with serial interface.
Considering you will be using the board linked. It is driven by transistors, so you can use the shift registers.
For the power supply, if you will be operating all of the relays at the same time it will draw about 650 mA (9x72mA), you will need a separate 5V power supply for the relay board, as I believe drawing that much current will heat the board and regulator a lot. If one at a time it will not draw too much, so its possible you can run it all off the Arduino.
A forum post of someone running 360 relays with shift registers.