I was curious to see that the word for "superstition", 迷信{めいしん} contains a character meaning lost, perplexed, or astray. Given that Japan and China both have a history of religious belief, I found the character choice odd.
Superstition, be it as the English term "superstition" or as the Chinese term [迷信]{míxìn} or the borrowed Japanese term [迷信]{meishin} generally refers to a belief that isn't grounded so much in any cohesive, structured religion or spirituality, but instead is viewed negatively as ad hoc and often incorrect. Thus, the Chinese term arose as literally [迷]{mí} ("crazy, lost, confused") + [信]{xìn} ("belief").
Note that this is distinct from religious belief or faith, which are referred to variously as [信念]{shinnen}, [信仰]{shinkō}, or [信教]{shinkyō} (among other possibilities). These other terms do not include the 迷 kanji.
I couldn't find the etymology on Wiktionary, does anyone know where it comes from?
Looking more specifically at your question of "where does it come from", I note that the Kokugo Dai Jiten entry lists an earliest Japanese citation as 1889.
There are some two-character on'yomi terms in Japanese that were coined or reworked in Japanese and a re-borrowed into Chinese, as happened with the terms 社会 and 自由 (where both have modern meanings that are originally Japanese reworkings of older senses). However, most originate from Chinese.
While I cannot currently find any explicit Chinese source that lists a date of appearance for this term, I do see in the Wiktionary entry that it has Chinese-derived descendants in Korean and Vietnamese. The Japanese coinages or reworkings, where known, are listed as the parents of any Korean, Vietnamese, or Chinese (re-)borrowings, so it appears that 迷信 as a word arose in Chinese.