Just to make it clear, this is no Tutorial on how to do it. This is just a way me and a friend went for a game idea he had. It was a long and kind of self invented way to go, but it worked for us. We had some inspiration from the internet, but the creative process was mostly developed by our self. I also try to give an example, in short of course.
Second, at first this doesnt seem to answer your question, but later on you might see, that you try to go from step 0.5 to step 4. I just want to help you organize your steps you need to take from the start to the graphic concept.
So before you start going ham on your graphic ideas, you should start out with a general concept of your game. If you only got a good gameplay idea, how do you know what to draw?
Basically write up one page with the general description of your game, the platform, the gapic style, the story, mechanics, scenario etc whatever you can decide on right now. Give it a WIP titel, draw some explanatory pictures if necessary and so on. What is the general setting of your game? Serious, dark, dramatic, funny, silly... and keep it to one page. What genre should it be? Whats the target audience (this was the hardest part for myself).
If you have no idea what to write down for some of these topics, dont mind it. Leave it out for now.
Example: Titel: Vehicular Battles
You have control over a vehicle and its crew. You Command your crew by typing commands, send them to their positions or weapons. If an enemy reaches your commander/captain or your vehicle gets destroyed, you loose. The game should be silly and colorful. Also its a mobile game.
Now, read it and think about it. Does it seem interesting to play? Are there concepts that are contradicting or problematic to each other? You still got plenty of time to change things. You could (and should) ask a friend, what he thinks of it so far. What does he like or dislike so far.
For Vehicular Combat: Typing on a phone for playing could be problematic, as the keyboard could block most of the screen, also it could be slow or with autocorrect problematic or to easy. We could change it and instead command the crew RTS-Style with tapping and sending them to their places.
If you think that everything is to your liking, choose one thing you are still missing, like in your example the scenario. Write down a list of every thing you can think off, even if at first its seems impossible to fit to your existing ideas. Think of cool books, films or tv series you like. Sometimes crossing two elements might also be interesting, just because no one has ever thought about it.
Write a list for every aspect your are missing. Then pick one aspect, either by personal preference or at random, and pick something from that corresponding list.
For example you are still missing a scenario, so take the scenario list. Then again pick something interesting or something at random. Would that scenario contradict your already Chosen elements? Or maybe you could cross some scenarios to make it even better.
Vehicular Battle: A fitting scenario could be near-future militaristic combat. Giant tanks battle like ships on land. This would be a problem for a colorful and silly game play. Even a Post-Apocalyptic scenario seems blend, if you think of colors, although possible silly game ideas. But what about prehistoric dino battles, where your cavemen crew rides on bases strapped to dinosaurs. Silly and colorful. Or Steampunk Space Battle with wizards as weapons?
Did you find one or more of those interesting, mark them, maybe rank them and choose one for the next step. Continue with the next list and do the same. If you cant find a fitting entry in those list, go back to a list before and change it.
I must admit, this was a very strenuous work. Working with a friend helped here, as even if at first something doesnt seem to fit, maybe your friend got an idea that could work out.
So, after you got all this done. Read your updated general concept again. You still can change elements, as long as the new element doesnt contradict an other element.
Vehicular Combat: (new Titel: Dinossal Combat)
Story: You are the mightiest and strongest man of a prehistoric tribes. You tamed dinosaurs to work for you and hunt for you. Your tribe is in constant conflict with other tribes, you so mount giant dinosaurs with wooden fortresses and fight other tribes with their fortress, battle for food or capture the females..
Gameplay: Vehicular Combat is a singleplayer game. You build a fortress fitting on a giant dinosaur, you add tribesman as crew and other smaller dinosaurs as weapons. After that you can choose missions with different objectives: Fortress Battle, Food Hunt or Capture the womans. While on mission, you change to a top-down view of the battlefield and you can control your crew in rts style. You can order your crew by clicking (or touching) them and send them to a certain place, weapon or station. Your crew can do some tasks: order the beast to move to a certain point (Dino handler)(insert picture of battle field), your crew can mount weapons or if close enough battle in hand to hand combat. Dinosaur weapons can have different effects, like throwing stones or tribesmen, or grabbing enemy tribesman or something from the ground in close range. Dinosaurs can be damaged and destroyed (freed and in panic). Combat itself is kind of slow at the beginning, but starts to get hectic as enemies get closer, your base dinosaur gets faster in a straight line.
After the Mission, you can upgrade your crew, add weapons or train your already added weapon dinosaurs.
You loose a mission, if everyone of your tribesmen die or your fortress dinosaur.
Style: Everything should look super bright, dinos are colorful, you hear cheering drums from off screen, 'uga Buga' when you command your crew and posh dinosaurs talking english. Everything should look super round with few hard edges. Characters should seem vague and with few details, while dinosaurs should have many funny details, like giant tails wrapped around their body (grabber dino) or posing like body builders with one big and one small arm (tosser dinos)
NOW, you can do your concepts for graphic, gameplay, story etc. You are no longer bound to the one page restriction, but you should keep your page and start a new chapter. Start with the topic you find the most important, then work on the next one and try to keep everything you have already done consistent with what comes next.
Here you should add your concept arts under graphics or style or story or what seems the most fitting, even an own section.. Depending on the style of the game start with drawings of example (concept arts) or add 3D models in T-Pose or other interesting poses.
This is where your second question is answered. Start with the colors, as you already know what your game should become. Cheerful, depressing, stern... these with the addition of the scenario should be enough to work out a color palette.
On addition to the graphic style: Many games combine a certain game play mechanic with the graphic style. Twinstick shooters and side scrollers have mostly giant red blinking bullets to make them noticable and aid the player what to keep track off (imagine a bullet hell game with tiny baryle noticable bullets) On of the best examples is Ikaruga (you can absorb bullets of one color, but not of the other). Ego-shooters need well defined objects and enemies (imagine pixel art enemies on pixel art background without motion). Some games also need color coding for better gameplay, Baba is you and Beat Saber are two good and essential different examples.