Does coloring affect the perception of depth?
Yes, color and shading can certainly affect depth perception, as explained by wikipedia:


  Aerial perspective – Due to light scattering by the atmosphere, objects that are a great distance away have lower luminance contrast and lower color saturation. Due to this, images seem blurry the farther they are away from a person's point of view. In computer graphics, this is often called "distance fog." The foreground has high contrast; the background has low contrast. Objects differing only in their contrast with a background appear to be at different depths. The color of distant objects are also shifted toward the blue end of the spectrum (e.g., distant mountains). Some painters, notably Cézanne, employ "warm" pigments (red, yellow and orange) to bring features forward towards the viewer, and "cool" ones (blue, violet, and blue-green) to indicate the part of a form that curves away from the picture plane.


Here are a few examples:



The above is Manet's "Luncheon on the Grass" - and if you look at it briefly it seems the bathing woman is sort of hovering amidst the trio instead of rinsing herself off in the background. This is because the warmer colors flanked by more saturated greens in the grass around her "pull" her forward into the same space as the rest of the painting. Here, scale is one of the major cues that she should be in the background.



Above is Cezanne's "The Bay" and is an excellent example of how warmer colors (reds, yellows, oranges) are used to add depth when contrasted with cool colors (blues, greens, violets). The image works very well, and that's partially because of the colors chosen. You can almost draw a diagonal line between the warm and cool portions of the painting.


  I noticed that if I try to imagine a clear blue daytime sky contrasted with a clear night sky and ask myself which of the two appears closer, my intuition says the daytime sky appears closer. My next thought was, given that a night sky is mostly black, visually the only difference between the two skies is their color. So why is that I want to "blue" is closer than "black"? 


Well, there are many differences between the two! The daytime sky has numerous reference points - the horizon, mountains, clouds, airplanes, nearby buildings, etc. I would bet the reference points are the number one reason you perceive the daytime sky to be closer, as our brain is constantly taking them into account without us thinking about it. There are other cues, too: The daytime sky has a gradient to it - that is, the blue of the sky differs due to the curve of the atmosphere, and gradients increase depth perception with more saturated colors being perceived as closer (as opposed to the edges of the daytime sky, which are often less saturated). 

The night sky, on the other hand, is pretty much solid black (if you live in suburban or urban areas). The lack of a gradient or other colors immediately robs the observer of some depth perception, and because of the inky blackness of night the other reference points - the horizon, nearby structures, airplanes, clouds, etc. - can practically disappear, robbing the observer of additional depth perception.