Should I insert a colour bar if arbitrary units are used? In a journal article, is it advisable to insert a colour bar (i.e. an explication of the colour scale) in a figure if arbitrary units are used?
If the colour order is already stated in the legend, does a colour bar add additional information in this situation?

An example can be found in this abstract. Imagine that this figure was generated by colour-mapping a signal in arbitrary units, if the legend had specified that the colour scale goes from red (disordered) to green (ordered), would the colour bar have been useful?
I would definitely include the color bar.  It just makes things easier to read, since you can compare the displayed values directly with your eyes, rather than having to refer back to a written explanation.  The bar also lets you see how the colors shade into each other as you move along the scale.

If it seems awkward to have the color bar in arbitrary units, you can explain exactly how you came by the arbitrary units (such as "data scaled by the maximum deviation from zero").  Then you can give the bar scale a more quantitative meaning.  Or, you might go the other direction and just labels the ends "low" and "high."