What is the best way to average two colors that define a linear gradient?

Several answers suggest converting to Lab color space - which is probably a good approach for more complex color manipulation.

But if you simply need a quick way to take the average of two colors, this can be done in the RGB space. You just have to mind a caveat: You must square the RGB values before averaging them, and then take the root of the result. (If you simply take the average, the result will tend to be too dark.)

Like this:

NewColor = sqrt((R1^2+R2^2)/2),sqrt((G1^2+G2^2)/2),sqrt((B1^2+B2^2)/2)

Here's a great vid which explains why this method is efficient: https://www.youtube.com/watch?v=LKnqECcg6Gw

Take a look at the answers to this question.

Basically, you want to convert the colors into something called Lab space, and find their average in that space.

Lab space is a way of representing colours where points that are close to each other are those that look similar to each other to humans.

Averaging in HSL color space might produce better results.

I don't know whether taking a simple average of the components is the "best" from a perceptual point of view (that sounds like a question for a psychologist), but here are a couple of examples using simple component averaging.

The red-mustard-green one is ugly but the interpolation seems reasonable enough.