Press Start when selecting the character to manually pick a color scheme with the d-pad. While selecting the specific color, it will show you a combination of buttons like LP, MK (light punch medium kick). Pressing these buttons at the character select will instantly pick that color. For instance LP (I think) instantly picks the default color. It seems "random" because you're probably pressing different buttons; the actual palette any one button combo will pick is always the same for that character.
You can only change your color at character select, not in the middle of story mode or in the middle of a match. If you need to change between Versus matches, go back to character select when the option is given to you.
If you accidentally pick a color you don't like, hit Select to go back and pick a different color.