I have noticed that in many languages, words for "no", negative verb forms, etc. often begin with the sound /n/. Although I understand it is by no means universal, is there any relationship between these sounds in otherwise unrelated languages (e.g. English "no", Japanese "-nai", and many more), or is it purely coincidental?
From Online Etymology Dictionary's entry of "un"-
prefix of negation, O.E. un-, from P.Gmc. *un- (cf. O.Fris., O.H.G., Ger. un-, Goth. un-, Du. on-), from PIE *n- (cf. Skt. a-, an- "not," Gk. a-, an-, O.Ir. an-, L. in-), a variant of PIE base *ne- "not" (cf. Avestan na, O.C.S., Lith. ne "not," L. ne "that not," Gk. ne- "not," O.Ir. ni, Corn. ny "not").
So the theory is that the root (possibly *ne-) traces back to the Proto-Indo-European language, the theoretical ancestor of the Indo-European languages (including English, Latin, and the majority of European and Indian languages, with total of 3 billion native speakers), which is why you can observe that it's very common.
That said, Japanese doesn't belong to this group, so possibly it's just a coincidence. Seing from this list of translations of "no" in many languages, I don't observe it being common outside of Indo-European languages.
It is not actually the case that /n/ is especially common for negation across language families. Rather the n-negatives are a particular feature of the Indo-European languages, being inherited from PIE and retained in some form in the majority of the daughter languages.
Outside of the Indo-European language family, n-negatives are not especially common. Those that do exist are the result of coincidence.
You also add a lot more languages with shared cognates to your list when you also consider that the Proto-Tibeto Burman negation is *ma- and the Proto-Sino-Tibetan root was probably also *ma- (James A. Matisoff (2003) Handbook of Proto-Tibeto-Burman. System and philosophy of Sino-Tibeto-Burman Reconstruction. Berkeley, Los Angeles, London: University of California Press.).
There's no explanation for why the PST form should be a nasal and well as the PIE but it accounts for the possible nasal negative in the 500 ST languages.
It is true that nasals (n, m, etc.) are the most frequent option for negation. And while there is an easy explanation for the words for "mother" (which also mostly use nasals, and which follows from the first sounds made by babies), it is not that clear for negation. Here is a hypothesis:
The use of nasal phonemes in the negative in so many languages of the world must in some way be related to to prevailingly nasal character of the grunt.
The concept of common phenomena like appearing of /n/ in many negative particles devised by many languages is not a clear cut. Etymology, Philology and Historical Linguistics all seek to understand the diacronic evolution of languages and aim at describing and understanding why such phenomena might take place in historically unrelated languages. Consider the word "Cave", for instance, that is in English. In Arabic, which is a sematic language, totally unrelated, it is /kaehf/ the vowel is a digraph a (referred to as ash in some textbooks). In French, it is caverne/cavity but also in French it can be Grotto/ pothole (totally unrelated pronunciation), although English and french are quite related historically and developmentally. In Chinese (simplified), however, it is 洞 which is pronounced as /dòng/. A slightly careful inspection of the pronounced version, one can see that /d/ and /k/ are both stops just like grotto which begins with /g/ (voiced velar stop). Similarities and differences of these kinds would need a careful, intensive, cross-linguistic studies to understand the nature of language and how it develops. My own point of view is that the word 'no' is like a safe word that works in many different contexts to stop a danger or to imply negativity. A word like that must take short time to be produced, must be easy to produce, and must be easily discriminated from any other productions. "no" is comprised of two phonemes (i.e. short in length), /n/ is an Alveolar sound which, due to its ease of production, it is a phonetic universal (i.e. no language known to us does not have a /n/ in its phonemic chart), and using a nasal, which is very sonorous in acoustic nature, makes it catchy for the ears. However, this is merely my speculation, although it is a logical one. For more on nature of sounds, you can return to "Elements of acoustic phonetics" by Peter Ladefoged or "Introducing phonology" by David Odden