What effect does time dilation have on bodies orbiting close to Black Holes? As far as my (somewhat basic) knowledge of astrophysics goes in general the closer to a star your orbit gets smaller (because you travel less distance) and faster (because you're deeper in the gravity well and need to go quicker to avoid falling in.)

But what happens on bodies orbiting close to black holes and subject to time dilation as far as an external observer is concerned?

This question isn't about interstellar but it's a good point of reference. Take the water planet they drop onto where gravitational time dilation is enough to make 20 or 30 years pass to the external observers while only a few hours pass for them. (I don't know if this is a realistic rate(?) of time dilation.)

What would the apparent orbit of their planet be to the external orbit and what would his orbit appear to be for them? Even though he is further from the star would he complete more orbits in the elapsed time despite being further from the centre of the system? And would they appear to be orbiting "slower" than him from his point of view.

Out of interest, though perhaps a second question is more appropriate, how would the apparent difference in relative orbital speed affect rendezvous manoeuvres if at all?

For example would the standard decelerate and fall into a lower orbit still apply but the trajectory plotted from a static observer look weird as time dilation set in? Or would the manoeuvre have to be different to account for the apparent velocity difference? What would a non-circular orbit look like in this system when observed from a circular orbit?

Also is the velocity required for orbit so close to a black hole high enough that speed based relativity also comes into play?
Trajectories close to a black hole can't be approximated by Newtonian mechanics, General Relativity is needed. The black hole doesn't have a surface, but the Schwarzschild radius is point of no return. However it is not possible to orbit just above the Schwartzchild radius.

If you are less than 1.5 radii from the event horizon, there are no orbits. The orbital velocity closer to a black hole than 1.5 radii would be greater than the speed of light. Inside this radius, the faster you try to go, the less the centrifugal force you experience becomes, and so the faster you would fall towards the blackhole.

In fact you won't find a stable orbit closer than 3 radii from the black hole. If the black hole is spinning (as most younger ones are expected to do) the space around the black hole is dragged along by the spinning black hole. It is possible to gain energy by entering this region of dragged space around a black hole. This all means that a space ship can't remain in the region of ultra-intense gravity for many hours by orbiting, It can't experience (from the point of view of a distant observer) extended gravitation time dilation by orbiting a black hole only a few km above its Schwarzschild radius.

It is possible to approach closer than 1.5 radii. An outside observer would see the spaceship approach the black-hole in a spiral at very high speed, but not cross the event horizon. The orbit would not appear to be elliptical and it would appear time dilated. Outside of 1.5 radii the dilation would be less. 

Trajectories close to the black hole would have to be calculated using GR. Newtonian mechanics would not be a close approximation. The calculation in GR would be computationally intensive, since the GR equations can't be integrated exactly, even for a two body problem, so a numerical technique would have to be used. 

Provided you stay rather further from the black hole, then the usual Newtonian approximation is valid. There's no certain boundary at which Newtonian mechanics is a good approximation. It depends on the accuracy needed.

Remember also that the region close to a black hole is a violent region of space. It would be dangerous for a ship to be so close to a black hole due to the intense radiation produced by infalling matter, and tidal forces.