From "Getting started with the Arduino" I'm not sure if I can supply my own 5V supply direct to the 5V pin, or whether I should always use the 9V to the 9V in pin?
I ask this because I already have a 5V supply available, and it seems a waste to supply 9V to be reduced to 5.
Yes 5V into the +5V line works well. 
And what happens when you plug the USB cable in to download a program? Then both the USB power and the external power are 'wired' together, is this a safe and have predictable behavior?
I'm not a fan of directly supplying +5vdc to a standard Arduino board. Wiring voltage to an output of a unpowered voltage regulator is not something I've ever read about in a regulator data sheet. And I also have not heard anything good about wiring external +5vdc to USB power.
Not saying it won't work, but I would sure like to see chip and PC manufacturers authorized information sources for these kinds of configurations.
Lefty
I have done it many times in my Arduino, plugging the USB programmer while the direct +5V PS is connected. Nothing wrong in this, in case both voltages are right.
To be strict, there is a short circuit of the magnitude of the difference between both supply voltages. In case USB is +5,000 V and the other supply is +5.100 V, you get a shortage of 0.1V. This, divided by the impedance of the line that crosses between both supplies, gives you the current dropped.
Normally, not enough to worry about.