What are the Most Important Attributes?
1. The Tripod
The most important factor will certainly be the tripod. Telephoto shots taken with a great lens handheld will be inferior to shots taken with a mediocre lens on a middling-to-good tripod.
Good autofocus is almost indispensable if your subjects are moving (I'm going to assume they might be). In most camera systems, autofocus is a combined feature of the camera and the lens (that is, both items need to support autofocus).
3. Sensor Area and Pixel Density
If you want to fill the frame with far-away objects, it is financially more efficient (at least in 2012) to buy a crop-sensor camera. Buying a camera with a sensor 2/3 the size of a full frame is much cheaper than buying a lens with a 50% longer focal length.
A high pixel count allows you to crop your original photo and still end up with a reasonable image if the subject didn't fill the frame (as usually will happen for birds, for example).
4. Lens Focal Length
This isn't really the least important of the four attributes, but precisely how important it is depends on things like what you're trying to shoot.
If the object truly is far away, 200mm is probably not enough. Unless you're making images of aeroplanes or buses. A 300mm lens on a 1.5x crop sensor body gives a similar field of view to a 450mm lens on a full-frame body (the difference in sensor size affects the field of view but not the focal length of the lens).
Depending on what you're shooting, 300mm may still not be enough. You can either buy an even longer lens (this rapidly gets expensive) or use a teleconverter. A teleconverter sacrifices some image quality (for the Nikon 1.4 teleconverter this is normally imperceptible) and some light (a 1.4 teleconverter makes your lens exactly one stop slower, and a 2.0 teleconverter two stops slower, and so on). Because the teleconverter loses light and autofocus cameras normally don't autofocus at apertures slower than f/5.6, it's normally a good idea to apply your TC to an f/2.8 lens rather than an f/4 lens. Put another way, a 1.4 TC on an f/4 lens results in a lens which is 50% longer in focal length but it's f/5.6. Autofocus may not be so good on that lens. Better to start with an f/2.8 lens, which will become an f/4 lens with the addition of the teleconverter.
Illustrative Equipment Selection, With Explanation
To fully answer the question, we need to continue to think about budget because one of the things you need to figure out is which bit to spend what fraction of your budget on (and why). This is going to depend on a bunch of things you didn't state (including what size things you want to make photos of, how far away they are, and whether they are moving). I'm going to make a few (explained) assumptions and suggest specific hardware, below. The idea is that this gives you some idea of the trade-offs.
You specified a DSLR so I will ignore odder solutions like Nikon 1 with F-mount converter and 70-200 (total cost probably around $3000 or so).
The idea is to illustrate the ideas I mentioned above, by selecting some specific bits of equipment. There is no reason to choose one manufacturer over another particularly. I happen to have chosen a manufacturer whose gear I'm familiar with, but you could quite happily go with another system and get a good result by applying the same principles.
Assuming Nikon gear for illustration purposes, I will assume you spend $1300 on a Nikon D7000; of the current Nikon crop-sensor cameras it has the highest pixel density and probaby the best autofocus (unless the D300s is better).
Other manufacturers no doubt make cameras of similar features and price (though I don't know offhand which the comparable Canon DSLR is). You could also buy a second-hand D300s from KEH for a slightly more - which might be a good idea if focus speed is important, and focus speed will certainly improve sharpness for moving subjects.
If you really want to save money on this area you could get a D90 second-hand for about half the cost of a new D7000. But there is quite a gap between the two in terms of capability.
Your original budget was $1000 to $4500. We spent about $1300 so this leaves between $0 and $3200 for the lens. At the bottom end of the budget range you could get the Nikon 300mm f/4.5 AI-S lens, which is manual focus (around $220 at KEH). Bjørn Rørslett rates that lens quite well, though I have never used it. The downside is that if your subject moves it may be difficult to get an in-focus image (unless the objects move through a specific point - like race cars - allowing you to use focus-trap).
Higher up this price range you have autofocus lenses, which will be a better choice for moving subjects. At 300mm focal length we have the autofocus Nikon 300mm f/4 lens (around $1400 new) and the Sigma f/2.8 lens (around $3400 new). If you suspect that low light will be a big problem you will prefer the faster lens. If 300mm may not be long enough, you may need to get a teleconverter, and so again you would need the f/2.8 lens. Spending $3400 on the f/2.8 lens though leaves us no money for a teleconverter (if we need it - but then, if we do, the alternative to a TC is an even longer lens, which is yet more expensive) or a tripod (which we basically can't do without).
There is also a Nikon 300mm f/2.8 lens but it is outside the stated price range.
Supposing for the sake or argument you go for the autofocus Nikon 300mm f/4, that comes to around $2700 for body + lens. This should leave you enough money for support.
Support: Tripod and Head
As I mention above (and as described by Thom Hogan's article on selecting tripods) selecting a good support is important, and the longer/heavier the lens, the more important it is. A Gitzo tripod (around $500) is a great choice.
For long lenses, you can use a ball head but the ideal thing is something that allows the camera/lens to be easily pivoted (to point it at what you're making a photo of). It's also an advantage for the support to allow the centre of pivoting to be the same as the centre of mass of the combined lens/camera system. A
Wimberley head ($600) is the classic solution to this problem.
There are circumstances where using a tripod is infeasible, for example on some safaris. For those cases there are a number of other options. They are worse than but also cheaper than a tripod; they range from specialist bar/window clamps to beanbags (much much less effective than a tripod but better than nothing).
All told this comes to $3800 so we're all done with some cash to spare.