As an avid player of Dwarf Fortress, I would go for a fractal formula to generate the stars. Computer random is just not good enough, in my opinion. Borrowing from DF game again, I would add various steps to enhance the starfield such as randomizing the shape, color, size, glow, cluster (intentionally adding a clump of stars together).
If you wanna go with realism, also simulate gas background. Space is not white dots on a solid black background.
Finally, I would suggest you get some space images (from our old friend Hubble telescope) and try to copy it as faithfully as possible. Then play with the parameters to get to your liking (perhaps you want to make a game out of this).
P.S: I have not specified any coding language because I believe its not a question regarding code (its pretty basic) but a question of design. You WOULD be doing this much easier in Flash / Actionscript than Java, trust me.