put the video you want to be in the place of the green/blue in video track 1, put your green/blue screened video in video track 2, apply the appropriate keying effect to the green/blue screened video, look for "keying" in the help/manual for exact instructions.
If you want there to be a starry sky where there's blue/green screen, you could just shoot some video of a starry sky, or use a still image and do the same as above.
If you just want to add stars to the video I'd get a good still of a night sky, edit it in Photoshop or similar, take out the background black, so you have just the stars, then import this to Premiere over your scene and keyframe movement as needed.
You could use a matte to make sure the stars only show up in the sky, try a gradient towards the horizon so they blend in.
Panasonic SD9, Panasonic NVGS-75, Canon MV600i