I found something in Baidu Encyclopedia.
Originally 吹牛 comes from 吹牛皮 (blowing cow leather). In the old times,
people who lived along the Yellow River used cow leather to make
rafts, cuz the yellow river could easily destroy wood boats. However
there was no bumpers at that time. So it was strong people who were
responsible to blow air into the "leather bag" to make it a raft.
However, even the strongest man could not make it by himeself. So if
someone says "I can blow a raft by myself", he must be bragging. As a
result, people use 吹牛皮 to refer to bragging.
The photo comes from: http://www.chinavalue.net/Wiki/%E7%89%9B%E7%9A%AE%E7%AD%8F.aspx
When it was Yuan dynasty in ancient China, the mongolians loved riding
horses (cuz they conquered China and many other places with their
cavalry force). At that time, when a mongolian met another mongolian,
he would pat the other's horse, and say something like "nice horse".
It was the best way to make generals and officers of the Yuan dynasty
happy by saying "your horses are good". And when the mongolians ruled
China, this custom also came to China.
However, originally it was 拍马 (patting the horse), not 拍马屁.
Forgive my translate ^_^