Learn Russian: Я раздам всем по одной листовке.

When using the preposition по to mean 'each' (distributive meaning), the number 1 and the noun it modifies must take the Dative case. So, the nominative одна листовка becomes the dative одной листовке.

How would the phrase change if I wanted to hand out two leaflets to everyone?

It would become по две листовки. As you are learning in this lesson, the distributive по behaves differently depending on the number. For 2, 3, and 4, по takes the Accusative case for the number (две, because leaflets are feminine) and the noun goes into the Genitive singular (листовки).

The verb раздам looks like it comes from дать (to give). What exactly does the раз- prefix add?

The prefix раз- (or рас-) generally implies an action moving outward in multiple directions, or dividing something among multiple targets. Combined with дать, it changes the meaning from 'give' to 'hand out' or 'distribute'. It conjugates exactly like the irregular verb дать.

Why is the word for 'everyone' written as всем instead of всех?

всем is the Dative plural form of the pronoun весь (all/everyone). It is in the Dative case here because 'everyone' acts as the indirect object, representing the recipients you are handing the leaflets to.