Before you start reading this tutorial, I recommend making a big cup of coffee - it will be quite long :-)

So, to start, create new document (I made it 3200x2000 pixels) and fill background with solid black color.

To fill our sky with stars, we'll need some help of ContextFree. You can get it at www.contextfreeart.org.
I downloaded one of fractals and manipulated it so that it fits my needs. You can download my fractal file here: xmasnight.cfdg. Using this file, create several similar fractals (in ContextFree, hit Ctrl-R to refresh and get new variation) and saved them as PNG images (right-click and save as image).

Open all PNG fractals in Photoshop, copy and paste them into one document, so that each fractal is a layer. For each layer, set Blend mode to "screen". It will make stars blend together.

Repeat as many times as you like, until you get enough stars. (I used about 20 fractals). If your stars are wrong color, you can colorize them - hit Ctrl-U and adjust hue and lightness as necessary.

I wanted that the stars do not only fill entire image, but also create subtle "paths", or roads. For that, I used another fractal-generated image from ContextFree. Sorry I deleted the source file! But if you open ContextFree and open "cillasun" or "demo1" from examples menu, that might be OK too.

ContextFree generates black fractals on white background. I need only black fractal, with transparent background. Here's how: open PNG image in Photoshop, select all (Ctrl-A), copy (Ctrl-C), close (Ctrl-W), create new file (Ctrl-N), paste (Ctrl-V), switch to mask mode (Q), paste (Ctrl-V), sqitch back (Q), delete (Del).