How did the Bolsheviks gain power outside Petrograd & Moscow following the 1917 October Revolution?

The Bolsheviks didn't have much power following their coup. The country however was in chaos, and even the preceeding "bourgois" government hardly could control much (Kornilov mutiny is a good example). The Bolsheviks have made a great effort to encourage further chaos, as well as to promise everyone as much freedom as they want - and, following the Bolsheviks taking control in Petrograd and Moscow, almost every region rejected the (by now defunct) central authority and went under control of a local Soviet (i.e., local popular government). The Bolsheviks notably appealed to this state of affairs later, when claiming that they had no involvement in the execution of the royal family.

[The black book of communism][1] outlines the many mutinies and rebellions that the Bolsheviks had to crush in order to gain the control of the country. The anti-bolshevik forces were just as disorganized, which is why it took time for various white movements to emerge (Kolchak, Denikin, Yudenich, local separatist/nationalist movelents, ideological movements like that led by Makhno, etc.)

Remarks

• The well-known propaganda slogan with which Bolsheviks rallied into the revolution and which they promptly put in law after the revolution is "Land to the peasants, factories to the workers". This is essentially a promise for a liberal capitalist society, which had nothing to do with the communist agenda, but certainly appealed to the population.
• Similarly, revolution had much support among the intelligencia, particularly junior military officers, who played the key role in winning the civil war (e.g., "the Russian Napoleon" Tuchachevsky). Most of them were ignorant of the details of communist ideology, but believed that the change was necessary.
• As communist ideology implies "complete destruction of the existing social order", it would be strange to expect from Bolsheviks to rely on the existing government and social structures to establish their power - these are precisely the ones that they aimed to destroy. If they did use them, it was a tactical use. [1]: https://www.amazon.fr/Black-Book-Communism-Crimes-Repression/dp/0674076087

In the answer, I limit myself to two months, November-December of 1917.

What you have to realize is that the Bolshevik Revolution replaced one government of dubious legitimacy with another one. To make things more confusing, Bolshevik Government also declared itself "provisional." In theory, everything was supposed to be sorted out by the Constitutional Assembly, elections to which were held in November of 1917 (after the Bolshevik Revolution). In practice, in provinces, power changed to the local Soviets (again, confusingly, of several kind), not all of which were sympathetic to Bolsheviks.

It's important to note here that even before the Bolshevik takeover in October/November of 1917, Russia had "dual" power structure, effectively shared by the Provisional Government (and its local representatives) and Soviets. What happened locally after October/November is that this dualism had disappeared.

Here are few passages from the book by Richard Pipes, "The Russian Revolution" followed by ones from "A Peoples Tragedy A History of the Russian Revolution" by Orlando Figes.

1. From Pipes:

After the February Revolution:

On March 9, hardly more than a week after the new government had come into being, Guchkov, the Minister of War, cabled General Alekseev to Mogilev: "The Provisional Government has no real power of any kind and its orders are carried out only to the extent permitted by the Soviet of Workers' and Soldiers' Deputies, which controls the most essential strands of actual power, inasmuch as the troops, railroads, and postal services are in its hands. One can state bluntly that the Provisional Government exists only at the sufferance of the Soviet of Workers' and Soldiers' Deputies."

After the Bolshevik takeover (October/November 1917):

In the other cities of Russia, the situation followed a bewildering vari­ety of scenarios, the course and outcome of the conflict in each city depending on the strength and determination of the contending parties. (In the countryside, at this point, the October coup had no impact except to intensify land seizures; there it did not make itself felt until the fol­lowing summer.) In some localities, the Bolsheviks joined hands with the SRs and Mensheviks to proclaim "soviet" rule; in others, they ejected their socialist rivals and took power for themselves. By early November, the new government controlled the heartland of the defunct empire, Great Russia or, at any rate, the cities of that region. For the present the borderlands as well as the villages remained outside its reach. The stratagem of carrying out the coup in the name and on behalf of the Soviet concealed from nearly everyone its true significance. The illu­sion prevailed that the Soviet, the stronger partner in the dual power arrangement that had existed since February, had formally assumed full responsibility, and hence that nothing much had really changed. The illu­sion gained strength from the fact that the new authority called itself also a Provisional Government. In the original draft of the October 25 announcement declaring the deposition of Kerensky's cabinet, Lenin wrote "Long Live Socialism!" but he had second thoughts and crossed out the phrase, apparently to emphasize (for now) the image of continu­ity. The earliest official use of the word socialism occurred in a document that Lenin drafted on November 2. In the aftermath of the coup, the ruble lost one-half of its exchange value in terms of the U.S. dollar, but shares on the Petrograd Stock Exchange held steady. There was no panic even among the affluent.

The fall of the old Provisional Government caused few regrets: eye­ witnesses report that the population reacted to it with complete uncon­cern. The man on the street seemed to feel that it made no difference who was in charge, since things were so bad they could not possibly get any worse.

...The population of what had been the Russian Empire tore apart the state, the product of 600 years of historical development. By the spring of 1918, the largest state in the world had disintegrated into many overlapping entities, large and small, each claiming sovereignty over its territory. As in the Middle Ages, Russia turned into a realm of self-governing principalities.

The first to detach themselves were the borderland areas inhabited by non-Russians. Beginning with Finland, which declared its independence in December 1917, one ethnic group after another went its separate way, sometimes justifying its action with the right of "national self­ determination" proclaimed by the new government. But the centrifugal forces also affected Russia proper, as provinces, regions, and even cities asserted independence from central authority. The Bolshevik acceptance of the anarchist principle of soviet rule encouraged this process. Accord­ ing to one contemporary source, in June 1918 there existed on the terri­tory of what had been the Russian Empire at least thirty-three 'sovereign' governments.

2. From Figes (describing the dynamics within the local Soviets after the takeover):

In province after province the Right SRs had lost control of the Soviets to the extreme Left. In the northern and central industrial provinces, where the Bolsheviks and Left SRs could count on the support of most of the workers and garrison soldiers, as well as a large proportion of the semi-industrial peasants, most of the provincial Soviets were in Bolshevik hands, usually through the ballot box, by the end of October, and only in Novgorod, Pskov and Tver did any serious fighting take place. In some of these towns, especially where there was a garrison, the Bolsheviks simply used their military strength to oust the opposition from the Soviet and install their own 'majority'. Further south, in the agricultural provinces, the transfer of power was not generally completed until the New Year and was often quite bloody, with fighting in the streets of the main provincial towns (Orel, Kursk, Voronezh, Astrakhan, Chernigov, Odessa, Kherson, Ekaterinoslav, Sevastopol and others). In most places the extreme Left organized its supporters among the soldiers and workers into an MRC, which seized control of the government institutions after defeating the cadet or Cossack forces loyal to the city Duma. New elections to the ruling Soviet were then held which, in one form or another, were usually rigged. As in Petrograd, the SRs and Mensheviks often played into the hands of the extreme Left by boycotting the Soviet and these 're-elections'. Yet, without real military forces of their own, or a large and active citizenry willing to take up arms in defense of the democracy, they had little option. The political civilization of the provincial towns was not much more advanced than in backward peasant Russia and outside the capital cities there was no real urban middle class to sustain the democratic revolution. That was the tragedy of 1917.

There is a separate question regarding behavior and attitudes of the local bureaucracy. I will add few words on this later. (In short, they went on strike.) The situation was further complicated by the railroad strike declared by ВИКЖЕЛ (railroad trade union), demanding a power sharing between all the "socialist" parties (including the moderate Socialist-Revolutionaries, known as right-SRs and Mensheviks) and causing further fragmentation of the already fragmented country.

Edit: Regarding Petrograd's Stock Exchange (a question mentioned in your comment). By the Sovnarkom (Bolshevik's government) decree of December 29, 1917, stock and securities trading became illegal (the text, in Russian, of the decree can be found here), which means that Stock Exchange was shut down by that time. Nevertheless, something weird was still going on. Richard Pipes, writes, describes the period of March of 1918:

Although they [Russian-German peace negotiations] had no result, the mere fact of these negotiations taking place helps explain the puzzling equanimity of Russia’s business community toward a regime which openly threatened it with economic ruin and even physical annihilation. Russia’s bankers and industrialists treated Bolshevik pronouncements as revolutionary rhetoric. In their view, the Bolsheviks would either turn to them for help in restoring a collapsing economy or fall. So it happened that in the spring of 1918 the Petrograd Stock Exchange, formally closed since the outbreak of the war, [it's unclear why Pipes says this since he surely knows that the Exchange was reopen in 1917] suddenly came to life, as securities, especially bank shares, rose in over-the-counter trading. The optimism of big business, reinforced by Bolshevik overtures and the knowledge that the government was negotiating with Germany a trade agreement that would open Russia to German capital, caused it to turn a deaf ear to the pleas of White generals for financial assistance. In the spring of 1918, the White movement appeared to businessmen a hopeless gamble compared with the prospects of collaboration with the Bolshevik Government.