According to one source, the expression originally comes from racing, used in its most literal sense.  Another source claims that it has its roots in 明代, in a family of expressions including "火上加油".   Both agree, though, that "加油" became a general expression of encouragement through its metaphorical usage becoming more and more closely tied to the word by itself.  There is nothing in the meaning of the constituent characters themselves, however, that conveys the meaning of encouragement.  Not all Chinese words can have their current meaning explained in terms of their parts (like 肥皂). 

Source alleging origins in racing: http://zhidao.baidu.com/link?url=yiP6iAc0S-3VMztyCR8dID7OYfAskDbfmR8_jBZ0Zs9RXweUeYBLpzRYnNBNU5PyNcOLgyrxMKTaWGb49G3Xpa
Source alleging origins in 明代: http://www.xiexingcun.com/yuwenjianshe/ywjs2009/ywjs20090125.html