While each case is unique, and I can't say much about China or Cambodia, there are some common elements in communist power and support for it.

For start, Bolsheviks had before October revolution a very simple program - peace, land and bread. And after the revolution they did, more or less, fulfill it. Soviet Russia ended its engagement in First world war, peasants did get their land and urban poor did get employment. There was a Civil war, but with exiting the world war and other immediate measures they got enough good will from the people to pull through that. Stalin's purges begun after a period of New Economic Policy, that seemed to reverse much of revolutionary gains and reintroduce both inequality and exploitation. Also, revolutionary generation of communists was entrenched in mid and high management positions, and that blocked vertical mobility for newly educated generations. Therefore, purges were not only largely supported, but were in many aspects a popular movement. Stalin dealt with whomever he paranoid thought of as potential opposition, a degree of revolutionary egalitarianism was restored, and vertical mobility once again became possible. I believe that it was the purges that largely provided a strong enough support for Stalin to weather the Second world war. All those who were promoted through purges, felt their social position tied to the figure of Stalin.

(I don't have a single book or an author to support this view of Stalinism and purges, at least not so explicitly. But it kind of comes through works like Fitzpatrick's "Russian Revolution", and especially "Education and Social Mobility in Soviet Union 1921-1934", Neumann's "The Communist Youth League and the Transformation of the Soviet Union 1917-1932", and some others, although I haven't read anyone explicitly calling the Great purge a popular movement.)

In the case of much of European countries where communist came to power after Second world war, they did so in majority of cases without majority support. That doesn't mean that support was not significant, and it came from several sources. First, capitalism and parliamentary democracy were largely discredited in the 1930s due to Great depression and its manifest political failure before and during Second world war. Second, brutality of nazi occupations and the role of Red army in liberation (or "liberation" as the case may be) provided a great amount of prestige to the communists, accompanied with very real, physical power in areas liberated by Red army. Third, with few exceptions, those countries where communist came to power were largely agrarian, illiterate societies with very narrow layer of modern, urban social and economic structures. Within less than a decade, they were mostly modern, industrial and urban societies. That alone provided an unprecedented opportunities for vertical mobility, and communist egalitarian policies in education and social services enabled almost anyone to take advantage of that opportunities.

Finally, life under communist rule was not all that gray and dreary as we often imagine. Those systems did take away political freedoms, and severely limited consumption options, but at the same time they did provide social security and many avenues for intellectual self-actualization quite independent of the system itself, as long as it was not explicitly against communist rule. For insight into different life possibilities, modes of sociability and intellectual life in late or mature socialism, I can highly recommend and excellent work by Yurchak, "Everything was forever, until it was no more".

I would like to add a bit to Fucho's post by pointing out five causes (who doesn't like lists?) of the mass support for Communism found in Postwar Czechoslovakia--the only Eastern Bloc nation to bring the Communists to power by fair election (only to have the Communists from this position of power institute a coup--but that's another story).

1. As Fucho explained, the Soviet Union gained a great deal of prestige during the Second World War by liberating much of Europe from Nazi occupation.

2. Also as Fucho explained, "the West," "capitalism," and even "liberal democracy" lost much prestige during the 1930s. This was especially true in Czechoslovakia, the only liberal democracy to survive until 1938 that later joined the Eastern Bloc after the war. The Munich Agreement (the "Munich Betrayal" in Czech and Slovak historiography) had a great effect on Czechoslovak perceptions of their place in the world, leaving the Soviet Union as the only obvious benefactor for Czechoslovak sovereignty.

3. Czechoslovakia, which was certainly note agrarian and illiterate (the nation was one of the richest on earth before World War II; see the introduction to Prague in Black by Chad Bryant, especially pages 77+, for a description of the power of the Czechoslovak prewar economy in Central Europe), had a longstanding Communist party presence, and the party of course took advantage of the postwar political scene.

4. The Soviet Union, which had become involved in Czechoslovak politics during the war and which had liberated Czechoslovakia at the end of the war, exerted influence in Czechoslovakia, sometimes clandestinely. This became more important in 1948 when the Soviet Union pushed for and backed the Communist coup and therefore cannot alone explain the rise of popularity of Communism in Prague, despite the fact that many American politicians would ascribe the rise of Communism in Czechoslovakia solely to the machinations of the Soviet Union.

5. The United States, which Czechoslovakia had previously perceived as a sort of spiritual benefactor (the Czechoslovak Declaration of Independence, written by Czechoslovak founding father Tomas Masaryk, posited Czechoslovak democracy as another step in the internationalization of democracy that began with the American Declaration of Independence), not only backed the Munich Agreement but also abandoned Czechoslovakia to the Soviet Union at the end of the Second World War. Roosevelt and Truman agreed with Stalin that Czechoslovakia would reside within the "Soviet sphere," and while it was never made clear exactly what this meant, Truman made it a reality when he aborted an imminent American liberation of Prague (against the wishes of both Winston Churchill and the Czechoslovak foreign minister Jan Masaryk, Tomas Masaryk's son). Those Czechs in Prague who rose up against Nazi occupation in anticipation of the imminent American liberation, at least those who survived, were obviously stunned. Though this aborted liberation of Prague is largely forgotten in the history of WWII, it's effect on Prague's mentality should not be understated--Czechoslovak diplomats in the United States, as well as the American ambassador in Prague, later cited the aborted liberation as a "decisive" moment for the people in Prague, who would vote the Communist Party to power in 1946 (the Czech lands, and not Slovakia, voted the Communists into power).

Point #5 is mostly based on American sources, especially the Foreign Relations of the United States series, years 1938-1948, and to a smaller degree The United States in Prague: 1945-1948 by Walter Ullman. The other four points are standard Czechoslovak history.

Edit: This answers your "support from the masses" part of your question and not really the "support of the revolutionaries" that's in your title, so I'll add this: the violent history of the Soviet Union was but one part of the violent history of Europe and the world. Czechoslovakia had allied with the West, portraying itself as the extension of American and liberal democratic values into Central and Eastern Europe. True revolutionaries such as Zdenek Mlynar weighed the Munich Agreement and its ensuing violence against the violence of Soviet history and found more reason to join the Soviet cause (see the opening ten or so pages of Mlynar's Nightfrost in Prague for a chilling explanation for the acceptance of Soviet violence--it's probably exactly what OP was looking for).

In China's case, the revolution was really complicated.

The Qing Dynasty ended in 1911 with Sun Yat-Sen and the Xinhai Revolution, and the beginning of the People's Republic is marked on October 1, 1949.

In between, there was an ongoing civil war between the nationalists on one side - the capitalist folks who wound up in Taiwan, led by Chiang Kai-Shek - and the communists on the other, led by Mao Zedong (especially after The Long March). But their fighting was interrupted by the Sino-Japanese War and World War II. The invasion of Shanghai. The Rape of Nanking.

The KMT (the nationalists, Kuo Min Tang or Guomindang) were largely sympathetic with landowners, while Mao appealed to the peasantry... the people who worked the land. That sounds like a pretty straightforward communist vs. capitalist rivalry, except Chiang had actually spent time in Moscow. He and Stalin weren't friends, but there was an alliance (with some Game of Thrones-esque wheels within wheels going on). Mao, not so much in with the Soviets.

What the Chinese communists had was a great understanding of how propaganda works, how to create mass appeal, how to generate a cult of personality.

The famine, by the way, happened from 1958-'61 or '62, a decade after Mao's first rise to power. He really should have tumbled to the sidelines after that, but maintained enough influence to rise again and become the central figure in the Cultural Revolution - in part through publishing some really snappy slogans in a format nearly anyone could access.