How did 外国人 become 老外? From Baidu:


  老外，是中国人对国外人的一种俗称，类似与老张、老王、老李之类的称呼。称呼中加“老”显得亲热，比如“老乡”“老表”，称呼你老外，就像称呼老张老李那样，大大咧咧，随便亲切。过去中国人对外国人的称呼都是用在第三人称上，只有“老外”可以用于第二人称。


To translate, it says laowai is a colloquial term for foreigners, similar to nicknames such as laozhang and laowang. The word lao is added to sound friendly. In the past, Chinese used terms that address foreigners as third persons, the term laowai can be used on a second person.

From Wikipedia:


  Laowai is a commonly used Chinese mandarin word. It is the shortened,
  informal version close to wàiguórén 外国人 ("foreigner"), a better
  translation of Laowai would be "alien"... So Laowai 老外 is more of a
  neutral term which can be used as: "an obvious foreigner", "very
  exotic", or "adventive", "alien".


Based on the above, there are two lines of thought: one saying that 老 is added as an indication of friendliness to foreigners; another saying that 老 is added to indicate that a foreigner is "always" an outsider.

Does anyone know the exact origin of this term?
As Wikipedia mentioned, “老” is an empty prefix. Laowai is neither positive nor negative.

Actually, the word is often used to refer to a variety of races like Caucasians, Indians, Africans and Middle Easterners, who look drastically different from Asians. You will rarely hear a Chinese person call Japanese, Koreans and Filipinos 老外. That's why you hear some Chinese use this term even in the United States and Canada.

The word emerged in Beijing and became popular there. In southern China it is used less. 

What's the reason you hear this word used frequently in China? Because westerners attract more attention in the public as they look different. The quickest way to refer them is with 老外. Saying 外国人 is too formal.

The word might become less popular when more foreigners start living in/visiting China. It'd be less strange to see them in the public. 

The word is also used less among those who are better educated. He has a name, why call him 老外? Regardless of whether the word is negative or not, saying such is not really polite.