You don't want to lose information, first and foremost. If a photo is overexposed to pure white or underexposed to pure black ("clipped"), there's nothing you can do about that lost detail -- it's gone forever. Getting the exposure "correct" means that you capture what you need to within the range capable of being recorded by the camera. There's typically a bit of wiggle room, though. I bet you'll find that you can often overexpose or underexpose by 1/3-1/2 of a stop and not lose much or any important information.
Sometimes you'll find you have more than a little wiggle room, with the histogram showing that only 2/3rds of the range is covered by your exposure. In that case: "expose to the right," or overexpose.
The Luminous Landscape article Expose Right explains this well. Basically, 1/2 of the tonal values available in a shot are used in the first stop (the bright near-white side), 1/2 of that becomes highlights, half of that becomes midtones, half of that becomes shadows, and 1/2 of that becomes black. By this example, the darkest of areas in your photo are only made up of 128 levels of variation while the brightest are made up of 2048. In other words, a bright photo contains a lot more variation (and therefore detail) than a dark photo does. All of that extra information from the overexposed photo allows you to correct it and create a better result than an underexposed photo does.