You don't need an Uno for that - the smaller 5V, 16 MHz ProMini will be sufficient, and use less power too. Run from 3 AA battery, 4.5V connected to Gnd & VCC pin.
(I'd say 3V/8MHz, but 3V may insufficient to light the Blue LED).
Hardware wise is simple - common anode RGB LED, 3 resistors. Anode goes to VCC, Resistors go between cathodes and PWM pin 3,5,6.
This one will be nice & bright!http://www.dipmicro.com/store/LED10AC
Red - 2V resistor = (4.5V - 2V)/.02 = 125 ohm
Green - 3.2V resistor = (4.5V - 3.2V)/.02 = 65 ohm
Blue - 3.1V resistor = (4.5V - 3.1V)/.02 = 70 ohm
Do simiilar math for the other LEDs you select.
Do some ordering, some building, come back for coding help.