We'll start with this large mass of stars (twenty thousand, to be precise) formed into a disc. A star's position is determined simply by choosing a random distance from the center and a random angle along the disc, plus a bit of vertical variation which increases towards the center to create a bulge at the core. There's also some bias in the function so that it's more likely to create stars near the center.
The colors of the stars are actually chosen by, for each star, randomly determining its classification (white dwarf, main sequence, giant, supergiant), then randomly choosing its age. Based on that information we can calculate a plausible color and absolute magnitude for the star based on the handy Hertzprung-Russell diagram. The probabilities are jiggered so that main sequence stars are more likely outside the galactic core, and star ages in general are higher in the core.
Now we go back and instead of just choosing a random angle along the disc for each star, we'll choose one of five equally spaced "arms" and choose a random distance from the arm's center. Again, there's some bias so stars are denser along the center of an arm.
Twisting the arms is simple: add the distance from the center to the computed angle.
Oh, and it looks better if we throw in about a thousand "nebulae" placed in a similar fashion to stars, and scaled to get smaller towards the edge of the disc. Now we're pretty close to the stereotypical mental picture most people have of a galaxy.
The end result looks pretty good, all in all, and doesn't take outrageously long to render. If you further increase the number of stars to 100,000, it still renders fast but breaks down a bit visually -- with that many sample points, the bias functions I'm using to place the stars start to show through. 20,000 or so is probably plenty, though. I'm toying with a game design vaguely inspired by the old Amiga classic Captain Blood; that game had 32,768 star systems, which is frankly more than enough.