There's really no one way that I start a digital painting. Many people have asked, so I did a short list of how I start my images. I don't think it's all of them as no one method seems to work the best for me. If I'm not getting anything with one method, I'll switch to another method and try that.
You can create a digital painting by starting it with a Base, apply Color, then apply Texture. You use a variety of brushes the entire time no matter if you're on the base, the color, or the texture pass.
Start with a Base:
1. Paint in grey scale. Use subtle variations in the value. Make sure you use a wide range of value say from 2 to 8. Also, vary the values during the transition. For example, if you're painting 3, add value 2, and some value 4.
1.1 Grey Scales with an Image Overlay. Slap down some gray values, overlay an image that's close to the colors you need. Use regular layers to further define the image. I find this method often leads to many surprises. Just go with it.
1.2 Use an existing image gray scale. CTRL-Shift-U to convert to black and white. Mark the gray scale up more. Keep marking it up until you see something. Further render it out in grey scale.
1.3. Start with a random texture type brush. Find something in the randomness. Render it out into grey scale, apply color.
2. Start with an image. Use lasso tool to randomly cut the image. Rotate the selection. Repeat until you "see" something. Use layers to further define the image. Switch to gray scale if it helps. If you use this method, pick a light cyan blue and with a soft brush, push back the values. This helps establish some initial distance in your image.
2.1 Start with an existing image. Pick colors directly from the image to work them into a new image. Keep marking it up until you see something.
2.2 Start with a collection of images, randomly arranged on your page. Slap around the color randomly, use the selection tool, etc to pull out interesting shapes until you see something.
3. Undercoat. This is like gray scale, but it's using a monotone color. I find that colors are more harmonious using this method. This is still just an experiment for me.
1. Use color dynamics with hue jitter at about 10% for color variation. Use regular layers to further define the image.
2. Paint directly on top of the base image. I use this when most of the colors are already on the image.
3. Use soft light layer to slightly saturate and brighten the color
4. Use multiply with a gray value to take the existing color and basically add the gray value to it. This works great for shadows.
1. Use existing images for texture. This takes a different type of skill. Like setting the image to overlay, playing with the levels to achieve the value you need. Then erase out what you don't need.
2. Use Free Transform to reposition the image so it stays in perspective.
3. Use warp or liquify filter to bend the texture around the object you're texuring.