Key Frame Distance (please help!)

The keyframe distance is the maximum number of frames before the encoder inserts an i-frame, which is the highest-quality frame of an MPEG stream (ie, it has all the information for a single frame of video inside of it rather than relying on the frames around it to reconstruct). In between the i-frames are b-frames and p-frames, which are "difference" frames that reconstruct that frame of video by looking at the nearest i-frame and applying all the "difference" frames from that point forward (or backwards). The collection of an i-frame and all its connected p-frame and b-frames is called a GOP, or "Group of Pictures". So in essence the "keyframe distance" value determines the length of each GOP.

Note that Premiere automatically inserts a new i-frame for scene changes, irrespective of the keyframe distance value. This is to assure video quality at the start of a new scene since there wont be enough in common from previous b-frame and p-frames.

Generally speaking, the more i-frames you have, the higher the image quality of video, but also the larger the size of the video. So the value you choose for keyframe distance is a balance between the file size you want the video to fit in vs quality. If you're not concerned with file size or the file size generated is within reason then you can just leave it to its default value. Otherwise you can tweak it as part of the process to get the file size down to where you want it to be (in combination with the other encoder parameters such as bitrate).

Which CODEC are you using?