I think you're going to have to study up on keplerian mechanics and vector maths. Objects in Celestia are in elliptical orbits, so they're not always moving at the same orbital velocity.
You'll need to work out the velocity and direction of each object at a point in time, each expressed as a 3-dimensional vector, then you should be able to subtract one vector from the other to give the relative velocity.
Here's a reference for the Vector math:
http://www.sparknotes.com/physics/vecto ... tion1.html
You should also find what you need on the keplerian stuff at that site as well.
I don't know of any way in Celestia to just plug in orbital elements and get out relative velocity, so you might have to do the math (I suggest a spreadsheet, once you've worked out the formulae you need, to make it easier on yourself.)
Sorry I can't be more help, but that's how I'd attack it. If anyone knows a better way, jump in!
