During game play, pause the game and press the SELECT button to change your character's outfit colors. Keep pressing select to cycle through all 8 palettes.

BTW: In the new version of Strider 1 Arcade bundled with the Playstation's Strider 2, after beating the game, you can go back in and change your character's gi color in player setup. Run Sabre's gameplay is obviously inspired by Strider, but it's a nice game to grab.