Like Daemaro said, you can´t re-size a low rez image to high rez one without losing quality.
My suggestion would be for you to create a new document in PS at like 2000pixel resolution and place the graphic shown as a guide on Background. You will have to scale it to fit the high rez.
Then start again and do all the art againn....save as a PSD file and export for web as JPG or PNG
I'm not sure what you're saying? It's impossible to increase the amount of pixels while maintaining the quality of the picture. Pixels are exactly related to the quality. More pixels is better quality assuming the image starts that way. When you blow up an image by making it larger you're stretching it over pixels. It'd be like taking a balloon with a drawing on it and stretching it over a bowling ball. The picture is going to get distorted. No way to avoid it.
Only thing I could suggest would to be just slap it on a black background, center it and copy/paste some stars around. I know the blue part doesnt exactly end but maybe you could attempt to tape it out.