This is a good question because it involves the concept of reference frames. The quick answer is that relative to you, the bullet will always travel at the same speed. In other reference frames, however, unexpected things can happen!
You may have heard of Newton's first law:
"Every body persists in its state of rest or of uniform motion in a straight line unless it is compelled to change that state by forces impressed on it."
We could rephrase this a little and say that a body in motion tends to stay in motion and a body at rest tends to stay at rest unless acted on by an external force.
Imagine you are on a perfectly smooth speeding train, moving at a uniform speed (not accelerating or turning), in a car with no windows. You would have no way of knowing how fast you are going (or if you were moving at all). If you throw a ball straight up in the air, it will come straight back down whether the train is sitting still or going 1,000 mph. Since you and the ball are already moving at the same speed as the train, the only forces acting on the ball are your hand and gravity. So the ball behaves exactly as it would if you were standing on the ground and not moving.
So what does this mean for our gun? If the gun shoots bullets at 1,000 mph, then the bullet will always move away from the gun at 1,000 mph. If you go to the front of a train that is moving at 1,000 mph and shoot the gun forward, the bullet will move away from you and the train at 1,000 mph, just as it would if the train were stopped. But, relative to the ground, the bullet will travel at 2,000 mph, the speed of the bullet plus the speed of the train. So if the bullet hits something on the ground, it will hit it going 2,000 mph.
If you shoot the bullet off the back of the train, the bullet will still be moving away from you and the gun at 1,000 mph, but now the speed of the train will subtract from the speed of the bullet. Relative to the ground, the bullet will not be moving at all, and it will drop straight to the ground.
What's true for bullets, however, is not true of some other things that you might "shoot" from the front of the train. A great example is sound waves. If you turn on the stereo in your living room, sound waves "shoot out" of the speaker at the speed of sound -- something like 700 mph. The waves propogate through the air at that fixed speed, and they can go no faster. So if you put a speaker at the front of the 1,000 mph train, the sound waves will not depart the train at 1,700 mph. They cannot go faster than the speed of sound. This is the reason why planes traveling faster than the speed of sound create sonic booms.
Related HowStuffWorks Articles
More Great Links