EDIT: Oops, I assumed you were using the Cycles renderer. For the Blender Internal renderer, it's a little different.
This is also sometimes called "grain" or "grainy" which might help your research.
Not to worry, you CAN get a better result. This is just because you've not rendered enough samples. The AO bake gets its quality settings from the "gather" section. Increase the number of samples and you will have a better result. Try adding 5 to the number of samples, and if it's still grainy, add 5 again. Keep adding 5 until you either get a good result, or the bake takes too long ;-)
There's even more information in the Manual:
Samples
The number of rays used to detect if an object is occluded. Higher numbers of samples give smoother and more accurate results, at the expense of slower render times. The default value of 5 is usually good for previews. The actual number of rays shot out is the square of this number (i.e. Samples at 5 means 25 rays). Rays are shot at the hemisphere according to a random pattern (determined by the sample methods described above); this causes differences in the occlusion pattern of neighboring pixels unless the number of shot rays is big enough to produce good statistical data.