I am not sure about whether there is supposed to be a space on either side of the ~ symbol, or whether the symbol should be on both sides or one side. Is there a clear mentioning of this usage?
It depends on the style guide. However, most style guides I have found recommend putting the symbol with no spaces on either just the front or both sides.
In other languages I know, colon : is used for this purpose, and it looks very peculiar of Japanese to use this symbol for this purpose. Is this only in Japanese? How did the usage arise?
It probably is only used in Japanese (however, I cannot vouch for all languages). I believe what you are seeing is the corrupt form of the ２倍ダッシ(ダッシュ). I think that the
〜 symbol should not be used in more formal writing. As for the origin, the 国語審議会 is responsible for deciding the usage of punctuation in Japan (or at least the basis for all punctuation). Please refer to くぎり符号の使ひ方 from 1946 for the origin of the 2倍ダッシュ which was called ナカセン.