Isn't there a catch-22 in adverstising on decentalized networks?

Not when it's up to individual to choose the advertisements.

how do you coordinate advertising amoung so many sites?

My guess would be in much he same way all of these sites can be seen there or here, at the same time. It's only a Market interface and some UI tweaks. In my mind anyway. Unfortunately, coding and design isn't my forte.