How independent were the Eastern European countries from the Soviet Union?

How much influence did the Soviet Union have over the other Warsaw Pact countries?

From complete to none, this was contested or accepted in varying periods by the parties and other social groups within the Warsaw Pact countries.

Did Moscow directly control them, and direct what they did?

No, and yes. Late in WWII there was a request from a faction of Polish Communists for a Polish SSR. This did not come to pass. Instead multiparty state formations were set up with two major gaps in the political spectrum: anti-democratic parties were excluded, and social democratic parties were forcibly merged into workers' parties controlled by the Communists.

From 1944 through 1958 (more or less), the Soviet Union deeply coordinated policy with Warsaw Pact states. In fact, it is worth considering the Tito-Stalin split and the 1949 purges as a clear example of the limits of this moment of Soviet-Central European relations. Yugoslavia's involvement in Comecon planning collapsed overnight, and the Soviet Union prepared plans and conducted operations for [what would have been a fool-hearty] invasion of Yugoslavia.

The Soviet Union had sleeper agents in fraternal parties, it had non-agents who were more Stalinist than Stalin, and fraternal parties were regularly purged along with civil society.

Did they often disagree with the USSR over policy? If so, what was the outcome? What did incidents like the 1956 Hungarian Uprising and the 1968 "Prague Spring" say about how independent were they from the Soviet Union?

This period didn't end with the death of Stalin, but rather two lines in the Soviet Union on economic development competed in Poland and Hungary. The failures in Poland led to an independent-of-Soviet-policy communist formation seizing control of the state and defying the Soviet Union with the threat of armed warfare.

In Hungary the Stalinist faction conducted a coup against the Moscow installed Nagy line. What is perhaps most important to this question from the ensuing revolution is that Hungarians sought socialism, democracy, continued but non-exploitative relations with the Soviet Union and did not wish to be part of the Warsaw Pact. The last point was the trigger for the second Soviet intervention, however, it seems that independent workers councils were equally unacceptable. (See the depiction of social democratic revolutionary workers in the White book series for example).

The Soviet Union had established that there were limits to its power:

• The capacity for state violence against the Soviet Union was a limit (Yugoslavia, later China)
• That independent Stalinist parties could run independent economic policies if they had their National Army onside (Poland)
• That Socialist Humanism, multi-party socialism, democratic workers councils replacing central planning, and non-Warsaw Pact membership by bordering states were intolerable to the Soviet Union, regardless of the horrific military and international prestige prices (Hungary).

Hungary, incidentally, was forced to have an opportunist Prime Minister who was controlled from below by Stalinists. It took until 1963 for Kadar to purge the party of Stalinists and to release most of the communists imprisoned politically from 1956 (his instinct and inclination in this matter). So while Hungary won the right for an independent economic line within central planning's dictates, the Soviet Union continued to exert considerable internal policy pressure until 1963.

I'm reluctant to expand this answer, as my mastery ends in 1963 when the Revolution's reaction ended. It is worth briefly noting that the Czechoslovak reformers and workers avoided socialist pluralism, but still got it in the neck for the most cardinal crime: independent workers councils.