Sachverhalt:
A. Vor dem Kantonsgericht Schaffhausen ist das Scheidungsverfahren von Z._ und X._ hängig. Am 6. Oktober 2009 ordnete das Kantonsgericht für das gemeinsame Kind Y._ (geb. 2000) eine Beistandschaft nach aArt. 146 Abs. 3 ZGB an und ersuchte die Vormundschaftsbehörde der Stadt Schaffhausen um Ernennung eines Beistands. Mit Beschluss vom 16. November 2009 ernannte die Vormundschaftsbehörde A._ zur Beiständin. Auf Anfechtung dieses Beschlusses durch den Kindsvater hin bestätigte die Vormundschaftsbehörde mit Beschluss vom 26. November 2009 die Wahl und unterbreitete diesen Beschluss dem Volkswirtschaftsdepartement des Kantons Schaffhausen als Aufsichtsbehörde. Dieses hiess die Einsprache des Kindsvaters mit Verfügung vom 19. Februar 2010 gut und wies die Sache zu neuem Entscheid im Sinne der Erwägungen an die Vorinstanz zurück.
B. Mit Beschluss vom 30. März 2010 ernannte die Vormundschaftsbehörde den Sozialarbeiter B._ zum Beistand für Y._. Auf Anfechtung des Kindsvaters hin bestätigte die Vormundschaftsbehörde am 8. Juni 2010 die Wahl und unterbreitete diesen Beschluss wiederum dem Volkswirtschaftsdepartement. Dieses wies die Einsprache am 2. Juli 2010 ab.
C. Am 19. Juli 2010 erhob X._ Verwaltungsgerichtsbeschwerde an das Obergericht des Kantons Schaffhausen (Verfahren Nr. xxxx). Er beantragte die Aufhebung der angefochtenen Verfügung sowie der Beschlüsse vom 30. März und 8. Juni 2010. Das Verfahren zur Beistandseinsetzung sei an die Vormundschaftsbehörde einer anderen Schaffhauser Gemeinde zurückzuweisen, eventuell sei Rechtsanwalt Thomas Lämmli als einziger Beistand, subeventuell als zusätzlicher Beistand von Y._ einzusetzen.
Mit Eingabe vom 16. August 2010 erhob auch Y._, vertreten durch Rechtsanwalt Lämmli, Verwaltungsgerichtsbeschwerde und beantragte, die Verfügung vom 2. Juli 2010 und die Beschlüsse der Vormundschaftsbehörde vom 30. März und 8. Juni 2010 aufzuheben sowie Thomas Lämmli als seinen Beistand einzusetzen, eventuell zusätzlich zu B._ (Verfahren Nr. yyyy).
Am 21. April 2011 hiess das Obergericht in separaten Entscheiden die Verwaltungsbeschwerden teilweise gut, bestätigte die Einsetzung von B._, setzte jedoch zusätzlich Rechtsanwalt C._ als Beistand ein. X._ und Y._ wurden die Gerichtskosten auferlegt, hingegen wurde die Vormundschaftsbehörde zur Entrichtung einer Parteientschädigung an die beiden Beschwerdeführer verurteilt.
D. Am 26. Mai 2011 hat X._ Beschwerde in Zivilsachen erhoben (Verfahren 5A_357/2011). Er beantragt die Aufhebung des Entscheides des Obergerichts hinsichtlich der Einsetzung der beiden Beistände und der Gerichtskostenauflage. Das Verfahren sei an das Obergericht zurückzuweisen; eventualiter sei Thomas Lämmli als Beistand von Y._ einzusetzen.
Am 30. Mai 2011 hat auch Y._ Beschwerde in Zivilsachen erhoben (Verfahren 5A_371/2011). Er beantragt die Aufhebung des Entscheides des Obergerichts hinsichtlich der Beistandseinsetzung. Sinngemäss verlangt er die Rückweisung des Verfahrens an das Obergericht zur Einsetzung von Rechtsanwalt Thomas Lämmli als Beistand; eventualiter sei Thomas Lämmli als Beistand durch das Bundesgericht einzusetzen.
Das Obergericht hat keine Anträge gestellt, aber dennoch zu den Beschwerden Stellung genommen. Z._ schliesst auf Abweisung der Beschwerden und die Vormundschaftsbehörde hat auf Stellungnahme verzichtet.

Erwägungen:
1. Die Beschwerdeführer fechten gesonderte kantonale Entscheide an, in denen es aber in der Hauptsache um dasselbe geht, nämlich die Ernennung eines Beistands für Y._ für das Scheidungsverfahren seiner Eltern. Es rechtfertigt sich deshalb, die beiden Beschwerdeverfahren zu vereinigen und im selben Urteil zu erledigen.
2. Die angefochtenen Entscheide betreffen eine der Beschwerde in Zivilsachen unterliegende Angelegenheit (Art. 72 Abs. 2 lit. b Ziff. 6 BGG) ohne Vermögenswert (Urteil 5A_493/2007 vom 20. August 2008 E. 1). Die Beschwerden wurden rechtzeitig eingereicht (Art. 100 Abs. 1 i.V.m. <ref-law>) und richten sich gegen die Entscheide eines oberen Gerichts, das als letzte kantonale Instanz auf Rechtsmittel hin geurteilt hat (<ref-law>). Zur Beschwerde ist berechtigt, wer vor der Vorinstanz am Verfahren teilgenommen oder keine Möglichkeit zur Teilnahme erhalten hat (<ref-law>) und durch den angefochtenen Entscheid besonders berührt ist und ein schutzwürdiges Interesse an dessen Aufhebung oder Änderung hat (<ref-law>). Als direkt von der Verbeiständung Betroffener hat Y._ ein schutzwürdiges Interesse an der Beschwerdeführung. Auch dem Kindsvater X._ kann ein schutzwürdiges Interesse hinsichtlich der Person des Beistandes nach aArt. 146 ZGB (AS 1999 1135) für seinen Sohn nicht abgesprochen werden, da der Beistand im Scheidungsverfahren Aufgaben wahrnimmt, die sich auf das Verhältnis des Kindes zu seinen Eltern auswirken (Antragstellung hinsichtlich der elterlichen Sorge, grundlegender Fragen des persönlichen Verkehrs und Kindesschutzmassnahmen gemäss aArt. 147 Abs. 2 ZGB [AS 1999 1135]). Die Beschwerde von X._ ist folglich zulässig. Ob auch auf die Beschwerde von Y._ eingetreten werden kann, braucht nicht endgültig entschieden zu werden (unten E. 5).
I. Beschwerde von X._ (5A_357/2011)
3. Der Beschwerdeführer rügt in erster Linie eine Verletzung der Ausstandsvorschriften. An den Beschlüssen der Vormundschaftsbehörde vom 30. März und 8. Juni 2010 habe Stadtrat D._ mitgewirkt, obwohl er sich im Ausstand hätte befinden müssen.
3.1 Das Obergericht hat hiezu ausgeführt, Stadtrat D._ sei bei den vorangegangenen Beschlüssen vom November 2009 in den Ausstand getreten, um den Anschein der Befangenheit zu vermeiden, weil er in einem Straffall von X._ zuständiger Untersuchungs- und Haftrichter gewesen sei. Es wäre widersprüchlich und nicht nachvollziehbar, wenn er nach Rückweisung der Sache an die Vormundschaftsbehörde nicht mehr in den Ausstand treten würde. Es seien somit Ausstandsregeln verletzt worden. Der Anspruch auf richtige Besetzung der Entscheidbehörde sei im Prinzip formeller Natur und es sei grundsätzlich gleichgültig, ob der Beschluss mit korrekter Besetzung gleich ausgefallen wäre. Eine Heilung sei jedoch ausnahmsweise möglich, wenn es einerseits um geringe Verstösse gehe, von denen angenommen werden könne, dass sie sich auf das Ergebnis nicht ausgewirkt hätten, und wenn andererseits der Rechtsmittelinstanz die gleiche Prüfungsbefugnis zustehe wie der betroffenen Behörde. Ein solcher Fall liege vor. Dem Obergericht komme volle Kognition zu. Der Ausstandsgrund sei nicht zwingend, sondern Stadtrat D._ habe bloss den Anschein der Befangenheit vermeiden wollen, ohne sich effektiv befangen zu fühlen. Sodann habe er nach seiner glaubwürdigen Darstellung als blosser Beisitzer auf den Inhalt des Antrages der stellvertretenden Schreiberin der Vormundschaftsbehörde keinen Einfluss genommen. Es sei deshalb davon auszugehen, dass sich der Verstoss nicht auf den Beschluss ausgewirkt habe.
3.2 Bei einer Vormundschaftsbehörde, die - wie vorliegend - Teil der Gemeindeverwaltung ist, handelt es sich nicht um ein Gericht im Sinne von <ref-law>, sondern um eine Verwaltungsbehörde. Wann Mitglieder einer Verwaltungsbehörde in den Ausstand zu treten haben, ergibt sich aus dem anwendbaren kantonalen Verfahrensrecht (vgl. <ref-law>; Urteil 5A_532/2007 vom 8. April 2008 E. 2.2) und aus den aus <ref-law> abgeleiteten Grundsätzen (Urteil 2D_29/2009 vom 12. April 2011 E. 3.2 mit Hinweisen). Die Gründe, die Stadtrat D._ dazu bewogen haben, in den Ausstand zu treten, sind nicht streitig. Die Berechtigung seines Ausstands bildet insofern nicht Verfahrensgegenstand. Im Folgenden ist deshalb davon auszugehen, dass Stadtrat D._ bei der Beistandsernennung für Y._ im November 2009 zu Recht in den Ausstand getreten ist. Dabei versteht sich von selbst, dass das Behördenmitglied den Ausstand weiterhin zu beachten hat, wenn eine obere Instanz - wie vorliegend geschehen - den ursprünglichen Entscheid aufhebt und die Sache zu neuer Entscheidung an die Behörde zurückweist.
3.3 Es stellt sich deshalb einzig die Frage, ob der Verfahrensmangel geheilt werden konnte, wie dies das Obergericht angenommen hat. Dabei ist vom Grundsatz auszugehen, dass ein unter Missachtung von Ausstandsvorschriften zustande gekommener Entscheid unabhängig von seiner inhaltlichen Richtigkeit aufzuheben ist (Urteile 2A.364/1995 vom 14. Februar 1997 E. 4, in: ZBl 99/1998 S. 289; 2C_732/2008 vom 24. März 2009 E. 2.2.2; 2P.152/2002 vom 12. Dezember 2002 E. 3.2). Nur ausnahmsweise kann von einer Aufhebung des Entscheides abgesehen werden, wenn die Ausstandspflichtverletzung im Verwaltungsverfahren nicht schwer wiegt und ein Einfluss auf den Inhalt der Entscheidung ausgeschlossen erscheint (Urteil 1C_378/2008 vom 27. Januar 2009 E. 2.7 mit Hinweisen). Dabei genügt der blosse Umstand, dass die übergeordnete Instanz über dieselbe Kognition verfügt wie diejenige, bei welcher der Fehler eingetreten ist, für eine Heilung noch nicht (Urteil 2A.364/1995 vom 14. Februar 1997 E. 4, in: ZBl 99/1998 S. 289).
Vorliegend kommt eine Heilung nicht in Betracht. Dass das Obergericht den Ausstandsgrund als nicht zwingend bezeichnet, macht die Verletzung nicht zu einer geringfügigen. Entweder ist der Ausstand begründet und zu beachten oder er ist es nicht. Wie bereits ausgeführt, kann die Begründetheit des Ausstands nicht überprüft werden, so dass davon auszugehen ist, dass Stadtrat D._ wie bereits zu Beginn des Verfahrens in den Ausstand hätte treten müssen (oben E. 3.2). Er hat an den Beschlüssen vom 30. März und 8. Juni 2010 zumindest insofern mitgewirkt, als er im Zirkulationsverfahren die Anträge unterzeichnet hat. Es kann sein, dass er diese Anträge inhaltlich nicht beeinflusst hat und dass die Beschlüsse bei Unterzeichnung durch ein Ersatzmitglied genau gleich ausgefallen wären. All dies ändert jedoch nichts daran, dass die fraglichen Beschlüsse nur mit seiner Zustimmung zustande gekommen sind. Unabhängig davon, ob und inwiefern er sich mit den zu fassenden Beschlüssen auseinander gesetzt hat, war seine Mitwirkung entscheidend für ihr Zustandekommen. Wie sie bei ordnungsgemässer Zusammensetzung des Entscheidkörpers ausgefallen wären, darüber kann nur spekuliert werden. Angesichts des grossen Ermessens der Vormundschaftsbehörde bei der Auswahl des Beistands kann jedenfalls nicht ohne weiteres unterstellt werden, dass die Wahl auf dieselbe Person gefallen wäre (vgl. Urteil 2A.364/1995 vom 14. Februar 1997 E. 4, in: ZBl 99/1998 S. 289). Dies zeigt sich bereits daran, dass auch das Obergericht von seinem Ermessen in dieser Angelegenheit Gebrauch gemacht und den Einsetzungsbeschluss abgeändert hat.
Die Beschwerde von X._ ist insoweit begründet. Der angefochtene Entscheid ist aufzuheben. Die Vormundschaftsbehörde der Stadt Schaffhausen wird erneut über die Einsetzung eines oder mehrerer Beistände für Y._ zu befinden haben. Bei diesem Ausgang des Verfahrens erübrigt es sich, auf die übrigen vorgebrachten Rügen (Verletzung des rechtlichen Gehörs und von aArt. 146 f. ZGB) einzugehen. Das Obergericht hat zwar die beiden Verfahren Nr. xxxx und Nr. yyyy nicht vereinigt und X._ hat das Urteil des zweitgenannten Verfahrens nicht angefochten. Die Urteile in diesen beiden Prozessen ordnen jedoch hinsichtlich der Beistandseinsetzung für Y._ genau das gleiche an. Sie können deshalb kein voneinander unabhängiges Schicksal haben. Die Aufhebung des Urteils im erstgenannten Verfahren zieht zwangsläufig die Aufhebung des Urteils im zweiten nach sich.
4. Der Verfahrensfehler, der zur Gutheissung der Beschwerde führt, ist bei der Vormundschaftsbehörde der Stadt Schaffhausen eingetreten. Es wäre deshalb unangebracht, Gerichts- und Parteikosten Z._ aufzuerlegen (<ref-law>). Vielmehr ist auf die Erhebung von Gerichtskosten zu verzichten (<ref-law>). Die Stadt Schaffhausen hat X._ angemessen zu entschädigen (<ref-law>). Das Obergericht hat über die Verteilung der bisherigen kantonalen Gerichts- und Parteikosten neu zu befinden (Art. 67, Art. 68 Abs. 5 BGG).
II. Beschwerde von Y._ (5A_371/2011)
5. Ist der angefochtene Entscheid aufzuheben (oben E. 3.3 am Ende), so entfällt das aktuelle und praktische Interesse von Y._ an der Beschwerdeführung. Seine Beschwerde ist als gegenstandslos abzuschreiben.
6. In einem solchen Fall entscheidet das Bundesgericht mit summarischer Begründung über die Kosten auf Grund der Sachlage vor Eintritt des Erledigungsgrundes (<ref-law> i.V.m. <ref-law> [SR 273]). Dabei ist nicht detailliert auf alle Rügen einzugehen (<ref-ruling> E. 4a S. 495; Urteil 5A_614/2009 vom 12. Januar 2010 E. 6).
6.1 Y._ hat im Wesentlichen dieselben Rügen erhoben wie sein Vater. Insbesondere hat auch er vorgebracht, dass Stadtrat D._ in den Ausstand hätte treten müssen. Wie gesehen ist diese Rüge begründet. Fraglich ist hingegen, ob auf die Beschwerde von Y._ überhaupt hätte eingetreten werden können, da ein elfjähriges Kind nicht ohne weiteres über die notwendige Urteilsfähigkeit für die selbständige Prozessführung verfügt. Ebenso wenig ist offensichtlich, dass der Streit darüber, welche Person als Vertretungsbeistand einzusetzen ist, die höchstpersönlichen Rechte des Kindes beschlägt. Beide Fragen brauchen hier nicht abschliessend geklärt zu werden. Bei der gebotenen summarischen Prüfung darf davon ausgegangen werden, dass das Bundesgericht wie die Vorinstanz auf die Beschwerde von Y._ hätte eintreten können. Selbst wenn dem Kind die Prozessfähigkeit abzusprechen wäre, erschiene es mit Treu und Glauben nicht vereinbar, es mit Kosten zu belasten, zumal die Vorinstanz auf seine Beschwerde eingetreten ist und seine Beschwerde vor Bundesgericht in der Sache gutzuheissen wäre. Dementsprechend ist auch hier auf die Erhebung von Gerichtskosten zu verzichten und die Stadt Schaffhausen zur Entrichtung einer angemessenen Parteientschädigung für das bundesgerichtliche Verfahren zu verurteilen.
6.2 Es ist unklar, ob Y._ die Anordnung des Obergerichts, ihm Gerichtskosten für das kantonale Verfahren aufzuerlegen, vor Bundesgericht mit der Hauptsache mit anfechten wollte. Zu seinen Gunsten ist der allgemeine Kosten- und Entschädigungsantrag jedoch in diesem Sinne zu interpretieren. Da das Bundesgericht bei einer Abschreibung infolge Gegenstandslosigkeit die kantonale Kosten- und Entschädigungsregelung nicht abändern kann, wenn diese nicht selbständig angefochten wurde, ist das Verfahren in diesem Punkt an das Obergericht zurückzuweisen (vgl. Urteil 5A_657/2010 vom 17. März 2011 E. 3.5 mit Hinweisen).

Demnach erkennt das Bundesgericht:
1. Die Verfahren 5A_357/2011 und 5A_371/2011 werden vereinigt.
2. Die Beschwerde im Verfahren 5A_357/2011 wird gutgeheissen. Die Entscheide des Obergerichts des Kantons Schaffhausen vom 21. April 2011 in den Verfahren Nr. xxxx und Nr. yyyy werden aufgehoben und die Sache zu neuer Entscheidung an die Vormundschaftsbehörde der Stadt Schaffhausen zurückgewiesen.
3. Das Verfahren 5A_371/2011 wird als gegenstandslos abgeschrieben.
4. Zur Regelung der kantonalen Gerichts- und Parteikosten beider Verfahren (Nr. xxxx und Nr. yyyy) wird die Sache an das Obergericht des Kantons Schaffhausen zurückgewiesen.
5. Es werden keine Gerichtskosten erhoben.
6. Die Stadt Schaffhausen hat X._ und Y._ je mit Fr. 1'000.-- zu entschädigen.
7. Dieses Urteil wird den Verfahrensbeteiligten und dem Obergericht des Kantons Schaffhausen schriftlich mitgeteilt.
Lausanne, 7. Oktober 2011
Im Namen der II. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Das präsidierende Mitglied: Escher
Der Gerichtsschreiber: Zingg