Often for molecules to form in interstellar space, dust is used as a catalyst. The reason is that in typical interstellar environments, densities are so immensely low that even for just two atoms to meet, the probability is so small that formation time scales are very long. For 3+ atoms, the chance decreases rapidly. Instead, an atom can stick to a dust grain and wait for ages until other atoms stick. The atoms slowly "crawl" around on the surface of the dust grain, eventually meet and make bonds. If the formation of a bond releases energy (is exothermic), the molecule can be ejected from the grain surface. This process is call adsorption.
The dust also helps shielding the molecules from stellar radiation which would otherwise easily destroy them. This is why molecular clouds are also very dusty. But actually UV irradiation helps with the formation of very complex molecules by ionizing less complex molecules that subsequently can make bonds with other atoms and molecules.
If the environments are extremely dense, as when a star dies and ejects its gas either as a supernova or a planetary nebula, molecules can also form. This is probably also how the dust itself is formed, although it might also be formed later on (this is currently debated; the problem is that supernovae are so powerful that their shock waves tend to destroy dust shortly after it forms, and planetary nebulae are created from stars that live so long that they can't explain the abundance of dust in the very early Universe where they wouldn't have had the time to live their lives).
As Stan Liou and LocalFluff says, methane is actually an "easy" molecule to form, both because it's rather simple, and because its constituents, hydrogen and carbon, are the most and the fourth most abundant elements in the interstellar medium, respectively.
In fact, far more complex molecules are regularly found in interstellar space, as can be seen on this list.
