Probes are kinda universal, almost all of the 20-500MHz scopes will have the same BNC connector, but you do have to pay attention to input capacitance and bandwidth. Bandwidth is less critical (more bandwidth than your scope is fine, less prevents your from using the scope to its full potential), but compensation range is relevant. If a probe can't compensate for your scope's input capacitance, it's unusable. But trimmer caps are not known for tight tolerances, so I have been able to compensate probes to scopes outside their specs in some cases.
Choosing A Probe (For Your Tektronix Scope) is a pretty good overview, nothing Tek specific about it. Get 10x probe, they are by far the most versatile. 1x probes are occasionally useful for measuring low-level signals, but their low bandwidth and huge input capacitance limit the usability (I only use them for power supply ripple measurement, and when amplitude accuracy is important, since they don't contain a divider). I'm not a big fan of switchable 1x/10x probes, although they're probably OK for low bandwidth <= 100MHz or so). Other kinds of probes, like 100x, current or active, are much more specialized, forget about them until you actually need them and are familiar with your scope.
Another place for free manuals is
KO4BB. Paying might get you a real paper copy or better quality scan (more readable, schematics on one page, searchable), but you can usually make do with a free copy if money's tight.
Tek 465 is a good scope, has been the workhorse of the industry for decades. But it's like to cost more than $50 by the time the auction finishes. The probes are not original but probably pretty cheap ones, but they'll work fine for most use. The operation and maintenance manual on CD are probably the same ones you can download for free from BAMA. I don't agree with Dave to dismiss HP/Tek beforehand, I'd just search based on price below $150 or whatever (advanced search).
I would look for completed auctions and watch the auctions for a while to get a feel for prices, don't jump on the first opportunity, it's unlikely to be the best. Scopes advertised as 'tested' will command a premium, but you'll know it's at least not completely broken. I wouldn't take part in the 'untested, don't know how it works, sold as is' lottery for a first scope.
Depending on where you live, looking for local deals on Craigslist might also be a good idea. Shipping heavy, fragile items like scopes can be expensive and might damage the item unless the seller packs very well.