What do I need to know about oscilloscope probes?
Oscilloscope probes aren't just pieces of wire with pointy end attached to them. Typical probe will in addition to the pointy stick and the alligator clip have the input attenuation circuitry and impedance matching circuitry inside.
Basically the oscilloscope input front-end has its own internal capacitance and its own internal resistance. In order to prevent signal distortion, the capacitance of the probe needs to match the capacitance of the scope. If it isn't well matched, you'll get overshooting or undershooting. Most scopes have on their front a probe compensation connector which provides test signal that can be used to tune the capacitance of the probe. Here's image of the effect:
The probe's resistance provides input attenuation and it works together with the input resistance of the oscilloscope. Usual 1x/10x probes will have a switch that inserts what's usually a \$9 \mbox{ } M \Omega\$ resistor in series with the signal. In the scope, there's usually a \$1 \mbox{ } M \Omega \$ resistor for input attenuation. In the 1x mode, you only have that resistor, while in the 10x mode, both resistors provide attenuation of \$10 \mbox{ } M \Omega\$.
In parallel with the probe's input resistance you have the compensation capacitor. When buying a probe, you should pay attention that the capacitor's value can match the value of scope's input capacitance.
Another important part of the probe is the tip capacitance. It's modeled as a capacitor in parallel with the signal. It's purpose is to slow down the rise time of the signal entering the probe, which is in general considered a negative effect. The tip capacitance probably won't be of too much importance for a scope such as the one you're considering, but for higher frequencies, it could cause problems when accurate measurement of rise time is needed.
Some probes have what's called high frequency compensation too. You probably don't want to pay for such a probe, but I'll just mention it for completeness. The high frequency compensation part will usually be in the BNC cable connector of the probe and consists of a series connection of a resistor and variable capacitor placed parallel to the signal path. It's used to fix problems with impedance increase with frequency due to cable inductance. Basically the impedance will decrease more or less linearly with the frequency until we reach the resonant frequency of the probe. After that, it will increase. The compensation system is used to move the resonant frequency point away from the frequency range we're interested in using the scope with.
Finally, there's a free book available from Tektronix (if you want to give them your e-mail address) which explains how probes work in great detail. It's called ABC of probes and is currently available from here.
What is too expensive?
I've had excellent experiences with the ultra-cheap $12 dealextreme oscilloscope probes:
They seem to be nearly identical to the probes that come with Owon Digital scopes, and for $12, they're practically disposable. I initially bought a pair out of curiosity, and they were nice enough that I have bought two additional pairs. The coax is very nice and soft and flexible, and they are good up to at least 10 Mhz (I don't have a faster signal generator at the moment), from my testing.
Dealextreme also has a lot of other scope probes, of varying speed rating, etc...
You can solder alligator clips to BNC connectors and get a "probe" that works at low frequencies. It won't work well at high frequencies, however. If you want to understand why, I suggest you read How does the current know how much to flow, before having seen the resistor?
Probes that will work well enough for hobby use up to 35 MHz (the limit of that scope, it seems) can be had for well under $50. Try MPJA. I've owned a pair of their 40 MHz probes for years, and they work at least as well as my cheap 30 MHz scope.