[Just wrote this draft, comments would be very welcome...]
What is the difference between Marxism and anarchism? Both are socialist ideologies, with many aims in common, and both are generally on the same side in the class war.
Both anarchists and Marxists believe that ultimately there should be no government by the state, that there should be free socialism. Anarchists believe that should be implemented at once, while Marxists believe it should be done in stages. In the first stage after the revolution, Marxists believe there should continue to be government by the state. Only after a transitional period, possibly a long transitional period, should the second stage be reached, when the state would gradually wither away and free communism be achieved.
Because the transitional state government would not rule over a capitalist system, it would not be a capitalist state but instead a 'workers state' or a 'dictatorship of the proletariat'. The idea is that that would gradually wither away over time, leading to the eventual anarchist style future society.
The withering away mechanism is not clearly explained, and there seems a great risk that it will not happen, and that the transitional workers state will become permanent. That was certainly the case in the historical record, and it was also warned of by anarchists such as Bakunin during Marx's own lifetime - warnings which unfortunately were not accepted. Millions of lives, along with the reputation and chances of success of the socialist movement, could have been saved had the anarchist fears and warnings been taken seriously.
It seems curiously naive for otherwise serious and knowledgeable revolutionaries to believe that a structure of centralised state power would voluntarily wither itself away over time. The experience of history is that the powerful never relinquish control except when forced to through revolution or the threat of revolution from the people they control. The various state socialist countries proved no exception. Recognising this, would leave no pragmatic option for socialism than libertarian socialism.
Marx's 'dictatorship of the proletariat' had a sinister ring to it even in his day, more so now given the terrible history since then. But in fact many Marxists, including Marx himself, did not intend it to mean an actual 'dictatorship'. They were only using exaggerated language to describe a minimal system of defence of the revolution - which anarchists do not disagree with. In that case, there is only a difference in terminology. But some Marxists really do want full blown dictatorship, replete with secret police and state terror. And unfortunately those have tended to be the types of Marxists who seized power in different places and times.
Also, although I stated above that "Both anarchists and Marxists believe that ultimately there should be no government by the state, that there should be free socialism", for some Marxists that ultimate end state is downplayed to such an extent as to mean that it is effectively removed from their programme. In that case, state socialism, as opposed to libertarian socialism, is genuinely their ultimate aim.
But it is important to note that there is continuity stretching from anarchism to left Marxism - the two ideologies in fact merge into each other. Autonomous Marxism and Council Communism have negligible differences with class struggle anarchism. And at least some modern Trotskyists are genuinely sympathetic to the need for democracy and freedom within socialism. In cases like those, it would be sectarian to fail to ally with fellow socialists over minor differences.
Organisational structures now are based on the desired structure of society after the revolution. Marxist-Leninists organise in centralised top-down parties, which are meant to be the vanguard of the working class, because after the revolution they want to see a centralised workers state. Some Marxist-Leninist parties (but by no means all) even resemble miniature versions of the worst Marxist-Leninist state dictatorships: with secretive leadership cliques, intrigues, denunciations, and cult-like uniformity of though. Anarchists organise themselves in decentralised autonomous local groups, federated from the bottom up through conferences with mandated delegates, because they want to see that sort of structure of government after the revolution.
Further reading - Anarchist FAQ, Section H, Why do anarchists oppose state socialism?