I had a slightly different take I thought I'd throw into the pile.
tl;dr:
The Machine will demonstrate superior decision making capabilities, and humanity will fall in line, single file.
One person at a time:
The machine makes good decisions. They might not always be perfect, but the machine would be like a super-sentient Watson; Cross-check available data, rank possible action is order of most-to-least likely to produce desired outcome.
Initially people would ask it things like a joke to cleverbot "Hey Multivac, how do I get my crush to like me back?". It would answer with something weird as shit: "Buy a pair of loafers, stand at the corner of 5th and Main, smile at your crush and make eye contact for 3 seconds. Post your results on spacebook, mytubes, and instasnap."
Using the massive database, Multivac can feasibly guess the emotional states and situational requirements required to answer most questions kinda-right. (You crush forgot to get his/her father a b-day present, and your thoughtful interception is the spark that carries you into matrimony.) All it needs to do is be right some of the time, and the true believers will convert the rest. Compared to religion, this machine will tap into that superstitious part of the brain too, while actually delivering visible results.
And when its wrong? Well obviously that person didn't follow the direction right. Look at the groupthink in AA or reddit - it's your fault when things go bad for you, not ours. People who don't get results aren't following direction well enough, and so they are totally at fault, not Multivac.
Nation-states:
"How do I get elected Senator?", "How do we secure peace in Iraq?", "How do we solve world hunger?".. Larger and larger questions will be posed to this machine, it will become a larger and larger recipient of both data and GDP. The answers will be mostly common sense stuff, but now they will actually get acted upon, because the fear from receivers of its wisdom will drive the populace to follow directions exactly, and they won't really notice that they gave up their agency.
Long-term:
At some point, either people will get disillusioned with the machine ("How do we fix local-valleys water shortage?" - "Genocide the Canaanites upstream."), or we will become so intertwined with it that we won't be distinguishable from separate entities (The Ultimate Upgrade), and so either way it won't last forever. But this is a good start. One correct decision (guess) at a time...