To get the full bandwidth out of your scope, you would use 50MHz or higher probes.
As a beginner, unless you're measuring very high frequencies or very fast rise times, you can probably get by with almost any set of probes.
The cheap options on eBay are:
- new Chinese imports (of uncertain quality)
- second hand brand name probes (make sure they're in working condition)
- NOS brand name probes.
When I got my 60MHz scope (without probes) I managed to pick up a set of NOS HP probes. They did cost me more than the scope, but the scope was pretty cheap
edit: On ebay, notice the difference in price between probes described as being "for HP or Tektronix" vs those that are described as either HP or Tektronix probes.
If buying a second hand probe, make sure that the ground clip is included. This is the short (typically black) lead connected near the pointy end of the probe with an alligator clip on it.