First, we're using unit called hertz to measure frequency and it is marked by Hz. Lower case m is for mili and upper case M is for Mega.
Next, you already noticed the first important parameter of a probe: It's frequency rating. The second important parameter is the compensation range for oscilloscope input capacitance. Your scope's input capacitance needs to be within that range, so that you can compensate for the scope's capacitance.
For very basic use, you should match the frequency rating and input capacitance with those of the scope and you can end the story here.
A little bit about more "advanced" use:
One more parameter of a scope probe is the attenuation ratio. Basically the probe reduces the input signal that many times. On the scope, you should select appropriate setting so that scope internally increases the signal amplitude to negate the attenuation. We need attenuation for two most basic reasons: To increase the impedance of the probe/oscilloscope system at higher frequencies and to be able to measure larger voltages.
Basically that input capacitance of the scope I mentioned earlier acts as if it is in parallel with the scope's input resistance of one megohm. The result if that high frequencies will be shunted to ground, so you'll basically have a low-pass filter in front of the scope. The probes with attenuation ratio greater than one have a large resistor connected in series with the tip. It will reduce the effect of the scope's input capacitance. Also it will reduce the loading on the circuit.
Most common probes, from what I can see, are X1, X10 and adjustable X1/X10 probes. Adjustable probes are handy, because you can view signals with very low amplitude using them in X1 position. This way, there's (almost) no signal attenuation before reaching the scope. Their down-sides are the fact that you can accidentally switch it from one mode to another and that they have a bit larger input capacitance.
Next we have the input capacitance of the probe. It acts as a capacitor in parallel with the probe tip and ground and it attenuates high-frequency signals. A little bit like the input capacitance of the scope. Generally, lower it is, the better the probe is.
Another potentially important part of probe selection are the miscellaneous features that the probe may have. Usually, there's a hook cover which goes over the probe tip. Size and shape of that accessory can be important, since some can be easily attached to DIP packages, while others may be too thick to be used on them. Others may have too small hook diameter to be used on thicker cables, should you ever need to handle that.
Next, you have the ground adapters for the probe. If you want to probe high frequency signals, you should use as short ground lead as possible, in order to avoid problems with its inductance. Pay attention to the type of insulation on alligator type ground clips. Some may have a square piece of stiff insulation material around the alligator clips, while others have round insulation. I like the square insulation better, since ofter in round insulation, the alligator clip can start rotating in the insulation as you try to press it. The square type insulations prevent the alligator clip from moving in the insulation. Some probes may come with a very short spring type ground connection as well, so consider them if you plan to work with signals of a bit higher frequency.
Then there are also special tip types for probes. For example, I noticed that I often bend probe tips by stabbing them into a breadboard, so I took probes with replaceable tips. Some probes may have little tip adapters for modern SMD packages available, if you need to use them or with tiny grabbers, so you can connect probes close together on a DIP package. Then there's the "minor" point of coaxial cable quality and length. Length usually increases probe capacitance. The "feel" of coaxial cable can affect use. Some stiffer cables may make probes move by themselves, as the cable attempts to move to its preferred position. This can make probing more difficult, especially if you can't use a hook or grabber type tip accessory.
Some oscilloscope probes come with little plastic rings that can be placed on the probe's BCN connector and the probe body itself. This way, you can easily see which probe is connected to which channel on the scope. If you ever get a digital scope with color screen, you can even match ring colors with channel colors on screen to make it even easier to see which probe is connected to what.
Finally, we need to take a look at the oscilloscope and the probe together as a test system. Oscilloscope's bandwidth is the so called "-3 dB point", that is to say the point at which you only see around 70% of signal's amplitude. If I remember correctly, same thing applies for oscilloscope probes as well. The result of that is that you basically have probe doing low-pass filtering on your signal and then you have the scope itself doing low-pass filtering on your signal. So if you want to get the most from your scope at high frequencies, you should get probes which have greater bandwidth than your scope, so that the scope isn't limited by the probes. I've seen an article from Agilent that explains how to calculate the bandwidth of scope and probe together as a system, but I can't remember its name now and I can't recall the formula
There's an interesting article from Tektronix called ABC of probes available on the Internet if you want to go into more detail on probe selection.