Well, this is a pretty simple and straight-forward project.
First you need to store your colours somewhere. Let's make 3 arrays for the different colour combinations. Say we want 4 colours:
#define COLOURS 4
int red[4] = {255,0,0,-1};
int green[4] = {0,255,0,-1};
int blue[4] = {0,0,255,-1};
The numbers are the brightness of the colour for each of the colour options. I have chosen to use -1 as a placeholder to mean "use a random value". So, colour 0 (the first column) has red = 255, green = 0 and blue = 0. The #define line creates a "macro" or symbol we can use so we easily know how many colours we have.
Now we need to set up the system:
#define DELAY 1000
#define RED 3
#define GREEN 5
#define BLUE 6
void setup()
{
 pinMode(RED,output);
 pinMode(GREEN,output);
 pinMode(BLUE,output);
}
Here we're defining which pins to use for which colour - you might want to change this to match your circuit.
Now we can do the hard work - making it light up. Now, I'm going to be fancy here and make it fade nicely between the colours.
void loop()
{
 // These are the current colour values
 static int currentRed = 0;
 static int currentGreen = 0;
 static int currentBlue = 0;
 // These are the colours we want to get to
 static int targetRed = 0;
 static int targetGreen = 0;
 static int targetBlue = 0;
 // These are some general variables for controlling the system
 int selectedColor;
 // Now let's drift the "current" colour towards the "target" colour:
 // Colour too dark:
 if(currentRed < targetRed)
  currentRed ++;
 if(currentGreen < targetGreen)
  currentGreen++;
 if(currentBlue < targetBlue)
  currentBlue++;
 // Colour too bright:
 if(currentRed > targetRed)
  currentRed--;
 if(currentGreen > targetGreen)
  currentGreen--;
 if(currentBlue > targetBlue)
  currentBlue--;
 // And now, if the colours match - this is where we pick a new colour:
 if((currentRed == targetRed) && (currentGreen == targetGreen) && (currentBlue == targetBlue))
 {
  // Let's hold the current colour for a second:
  delay(1000);
  // and select a new one:
  selectedColour = rand() % COLOURS;
  targetRed = red[selectedColour];
  targetGreen = green[selectedColour];
  targetBlue = blue[selectedColour];
  // Is the "target" colour -1? If so, set it to a random value:
  if(targetRed == -1)
   targetRed = rand() % 255;
  if(targetGreen == -1)
   targetGreen = rand() % 255;
  if(targetBlue == -1)
   targetBlue = rand() % 255;
 }
 // Now we have done our colour adjustments - let's set the actual LED to the colour:
 analogWrite(RED,currentRed);
 analogWrite(GREEN,currentGreen);
 analogWrite(BLUE,currentBlue);
 // And let's introduce a delay so the transition is nice:
 delay(10);
}
Now bear in mind that I wrote this code direct into the browser here, and haven't tested it. There may be (will be) errors. The theory should be sound though.