Remember, Rurouni Kenshin is set during the late 19th Century. This is just after the American Civil War, during the British Victorian Era: the height of the British Empire, and a time when the Western powers were very interested in the riches of the Far East.
The Western powers were mostly laissez-faire capitalists who would allow their people to trade anything with anyone; read about the British opium trade in China to get an idea of how trade worked at the time. Western traders would trade whatever they could for Eastern gold, silver, tea, and silk; that included guns, which were plentiful and relatively inexpensive in the West—the Japanese Meiji Era began just a few years after the American Civil War ended, and there were guns everywhere in America. The factories of Britain, France, and Germany were also constantly spitting out rifles, revolvers, and cannons. In this period, the European powers would still have a major war among themselves every few years (the Franco-Prussian War broke out during the same timeframe that Kenshin takes place), so they all wanted to build up stores of arms in preparation for the next struggle.
Given that guns were everywhere in the West, that they were highly desired in Japan, and that Western traders desired Eastern riches, it makes sense that the Western traders would trade guns to the Japanese. Although we don't see it in Rurouni Kenshin (to my knowledge; I only watched the anime up to the end of the Kyouto Arc), I always assumed these factions got their guns by trading goods like silk and tea to Westerners, or by buying them from Japanese merchants who had traded for them with Westerners. This did happen historically, as the article on Firearms of Japan linked by @nhahtdh tells us.
As for the regulatory side, things in general were much less regulated back then. The Western governments of this era had little power to regulate trade, due to corruption and cronyism. Even if they were able to regulate trade, they didn't have any incentive to do so; Western governments wanted their merchants to trade in Japan and bring the riches back home. The Japanese government had no power to regulate trade on its end either; it had seen what happened when the Chinese tried to stop the opium trade, and knew it could do almost nothing to regulate foreign trade until its military was modernized.
From what I can remember, the guns in Rurouni Kenshin are historically accurate to the period; the Gatling gun was very new at the time, having been invented during the American Civil War. Revolvers, like the famous Colt, were also common in the West. According to the article @nhahtdh linked on Firearms of Japan, firearms from before the Tokugawa period were matchlocks based on the Portuguese arquebus. Many of these were destroyed during the Tokugawa period, but some remained, and after the arrival of Perry, they were converted to flintlocks as part of the modernization effort (see also the fourth paragraph, here).