Sachverhalt:
A. Zwischen X._ und Z._ ist seit 2004 ein Scheidungsverfahren hängig. Am 13. Juni 2006 wurde X._ durch den Richter I des Bezirksgerichts Visp im Rahmen vorsorglicher Massnahmen gemäss <ref-law> zur Bezahlung monatlicher Unterhaltsbeiträge von Fr. 5'000.-- ab 1. April 2006 an Z._ verurteilt. Am 4. Februar 2008 erliess der Richter II des Bezirksgerichts Visp das Scheidungsurteil und verpflichtete X._ zur Bezahlung von monatlich Fr. 5'000.-- nachehelichem Unterhalt an Z._. Gegen dieses Scheidungsurteil erklärten beide Parteien die Berufung an das Kantonsgericht Wallis.
B. Bereits am 30. Januar 2005 hatte Z._ ihre zukünftigen Unterhaltsansprüche an den Kanton Waadt, Service de prévoyance et d'aide sociales, abgetreten. Am 5. August 2009 reichte Letzterer beim Kantonsgericht Wallis ein Gesuch um richterliche Anordnung einer Schuldneranweisung im Sinne von <ref-law> ein. Der Gesuchsteller verlangte, die S._ AG als Arbeitgeberin von X._ und jeden weiteren Drittschuldner anzuweisen, den monatlichen Unterhaltsbeitrag von Fr. 5'000.-- an den Gesuchsteller zu überweisen. X._ beantragte, das Gesuch einzig im Umfang von Fr. 1'350.-- gutzuheissen.
Mit Urteil vom 1. Oktober 2009 hiess das Kantonsgericht das Gesuch gut und wies die S._ AG an, den Lohn von X._ bis zu einem monatlichen Höchstbetrag von Fr. 4'912.-- bis zum rechtskräftigen Urteil in der Scheidung von X._ und Z._ an den Gesuchsteller zu überweisen.
C. Am 16. Oktober 2009 hat X._ (fortan: Beschwerdeführer) gegen dieses Urteil Beschwerde in Zivilsachen erhoben. Er beantragt aufschiebende Wirkung und die Aufhebung des kantonsgerichtlichen Urteils.
Mit Präsidialverfügung vom 19. November 2009 ist der Beschwerde aufschiebende Wirkung zuerkannt worden. Der Service de prévoyance et d'aide sociales des Kantons Waadt (fortan: Beschwerdegegner) hat unaufgefordert in der Sache eine Vernehmlassung eingereicht, sich zur aufschiebenden Wirkung aber nicht geäussert. Das Kantonsgericht Wallis hat auf eine Stellungnahme hinsichtlich der aufschiebenden Wirkung verzichtet.

Erwägungen:
1. Bei der Schuldneranweisung gemäss <ref-law> handelt es sich nicht um eine Zivilsache, sondern um eine privilegierte Zwangsvollstreckungsmassnahme sui generis (<ref-ruling> E. 1 S. 12 ff.), welche allerdings in unmittelbarem Zusammenhang mit dem Zivilrecht steht, so dass die Beschwerde in Zivilsachen grundsätzlich gegeben ist (<ref-law>; <ref-ruling> E. 1.1 S. 688). Da vorliegend einzig die Schuldneranweisung umstritten ist und damit vermögensrechtliche Interessen verfolgt werden, ist die Beschwerde streitwertabhängig (vgl. Urteil 5A_108/2007 vom 11. Mai 2007 E. 1.2). Entgegen <ref-law> enthält das vorinstanzliche Urteil keine Angaben zum Streitwert. Aufgrund der strittigen Differenz von monatlich Fr. 3'562.-- und der nicht abschätzbaren Dauer der Massnahme ist gemäss <ref-law> vom Erreichen des Streitwerts (<ref-law>) auszugehen. Als Zwangsvollstreckungsmassnahme ist die Schuldneranweisung ein Endentscheid (<ref-law>). Zugleich handelt es sich um eine vorsorgliche Massnahme im Sinne von <ref-law>, gegen welche ausschliesslich die Verletzung verfassungsmässiger Rechte vorgebracht werden kann (<ref-ruling> E. 5 S. 396). Der angefochtene Entscheid ist kantonal letztinstanzlich (<ref-law>) und die Beschwerde ist rechtzeitig erfolgt (<ref-law>).
Aufgrund des im Bereich der verfassungsmässigen Rechte anwendbaren Rügeprinzips ist in der Beschwerde klar und detailliert anhand der Erwägungen des angefochtenen Entscheids darzulegen, inwiefern verfassungsmässige Rechte verletzt worden sein sollen (<ref-law>; <ref-ruling> E. 6 S. 397; <ref-ruling> E. 3.2. S. 88 mit Hinweisen). Wird eine Verletzung des Willkürverbots - einschliesslich der Willkür bei der Sachverhaltsfeststellung (<ref-ruling> E. 1.4.3 S. 255) - geltend gemacht, muss im Einzelnen aufgezeigt werden, in welcher Hinsicht der Entscheid an einem qualifizierten und offensichtlichen Mangel leidet (<ref-ruling> E. 2.2 S. 246 mit Hinweis).
2. Das Kantonsgericht hat sich auf den Massnahmeentscheid vom 13. Juni 2006 gestützt und ist demgemäss von einem monatlichen Einkommen des Beschwerdeführers von Fr. 12'000.-- und einer Unterhaltsverpflichtung von Fr. 5'000.-- ausgegangen. Der Bedarf des Beschwerdeführers von Fr. 7'000.-- und das betreibungsrechtlich festgelegte Existenzminimum von Fr. 2'550.-- (Lohnkompetenz I) bzw. von Fr. 3'550.-- (Lohnkompetenz II) würden durch die verlangte Schuldneranweisung nicht tangiert. Die S._ AG als Arbeitgeberin des Beschwerdeführers könne somit gestützt auf <ref-law> angewiesen werden, den ganzen Nettolohn des Beschwerdeführers von Fr. 4'912.-- dem Beschwerdegegner zu überweisen.
3. 3.1 Der Beschwerdeführer rügt zunächst eine Verletzung des rechtlichen Gehörs (<ref-law>). Die Vorinstanz sei ihrer Begründungspflicht insofern nicht nachgekommen, als sie nicht dargelegt habe, wieso sie ihrem Entscheid das hypothetische Einkommen des Beschwerdeführers von Fr. 12'000.-- gemäss Eheschutzentscheid des Bezirksgerichts Visp vom 13. Juni 2006 zugrunde gelegt habe.
3.2 Teilgehalt des rechtlichen Gehörs nach <ref-law> bildet die Begründungspflicht. Die Begründung eines Entscheids muss so abgefasst sein, dass sich der Betroffene über die Tragweite desselben Rechenschaft geben und ihn in voller Kenntnis der Sache an die höhere Instanz weiterziehen kann. In diesem Sinne muss die Behörde wenigstens kurz die Überlegungen nennen, auf die sich ihr Entscheid stützt. Diese Minimalanforderungen gelten auch bei der Anordnung vorsorglicher Massnahmen (BGE <ref-ruling> E. 4.1 S. 88 mit Hinweisen).
3.3 Das Kantonsgericht hat die Abstützung auf den Massnahmeentscheid vom 13. Juni 2006 damit begründet, der Beschwerdeführer habe in seiner Gesuchsantwort selber ausgeführt, dass hinsichtlich der Einkommensverhältnisse von diesem Entscheid auszugehen sei. Das Kantonsgericht ist somit nicht veranlasst gewesen, seine diesbezüglichen Ausführungen näher zu begründen. Die Begründungspflicht ist folglich nicht verletzt. Ob das Abstellen auf den Massnahmeentscheid in der Sache haltbar ist, wird an anderer Stelle zu prüfen sein (unten E. 4.5 f.).
4. Der Beschwerdeführer wirft dem Kantonsgericht in mehrfacher Hinsicht eine Verletzung des Willkürverbots (<ref-law>) vor.
4.1 Willkür in der Rechtsanwendung liegt vor, wenn ein Entscheid auf einem offensichtlichen Versehen beruht, mit der tatsächlichen Situation in klarem Widerspruch steht, eine Norm oder einen unumstrittenen Rechtsgrundsatz krass verletzt oder in stossender Weise dem Gerechtigkeitsgedanken zuwiderläuft. Das Bundesgericht hebt einen Entscheid jedoch nur auf, wenn nicht bloss die Begründung, sondern auch das Ergebnis unhaltbar ist. Dass eine andere Lösung ebenfalls als vertretbar oder gar zutreffender erscheint, genügt nicht (<ref-ruling> E. 5.1 S. 17 f., 131 I 467 E. 3.1 S. 473 f.; je mit Hinweisen). In analoger Weise liegt Willkür in der Sachverhaltsfeststellung vor, wenn sie offensichtlich unhaltbar ist, zur tatsächlichen Situation in klarem Widerspruch steht, auf einem offenkundigen Versehen beruht, eine Norm oder einen unumstrittenen Rechtsgrundsatz krass verletzt oder in stossender Weise dem Gerechtigkeitsgedanken zuwiderläuft. Auch hier darf nicht bloss die Begründung, sondern muss das Ergebnis unhaltbar sein (<ref-ruling> E. 3.1 S. 178 mit Hinweisen).
4.2 Der Beschwerdeführer rügt zunächst eine willkürliche Anwendung von <ref-law>, weil die angeordnete Schuldneranweisung eine Eheschutzmassnahme sei, welche nach Rechtskraft der Scheidung gar nicht mehr erlassen werden könne. Er moniert in diesem Zusammenhang auch die ungenauen Sachverhaltsfeststellungen der Vorinstanz, aus welchen sich die Tatsache der Rechtskraft des Scheidungspunktes nicht deutlich ergebe, und reicht ein Schreiben des Kantonsgerichts vom 16. Dezember 2008 an das Bezirksgericht Visp ein, mit welchem die Rechtskraft dieses Punktes bestätigt wird.
4.3 Die Tatsache der rechtskräftigen Scheidung ergibt sich aus dem angefochtenen Urteil in sprachlich zwar sehr ungenauer Weise, doch lässt sie sich daraus sinngemäss immerhin ableiten. Angesichts dieses Umstands stellen sich weder die Frage der Berücksichtigung neuer Tatsachen (<ref-law>) oder der Berichtigung des Sachverhalts von Amtes wegen (<ref-law>) noch einer Rückweisung zur Ergänzung desselben (<ref-law>).
Dem Beschwerdeführer ist insofern beizupflichten, als die Schuldneranweisung gemäss <ref-law> eine Eheschutzmassnahme darstellt. Eine Eheschutzmassnahme setzt den Bestand einer Ehe voraus. Somit kann auch eine Schuldneranweisung gemäss <ref-law> nur während bestehender Ehe, nicht aber nach Rechtskraft des Scheidungspunktes erlassen werden (vgl. BRÄM/HASENBÖHLER, Zürcher Kommentar, 3. Aufl. 1998, N. 6 zu <ref-law>; HEINZ HAUSHEER UND ANDERE, Berner Kommentar, 1999, N. 24 zu <ref-law>; RENÉ SUHNER, Anweisungen an die Schuldner, 1992, S. 39 f.). Diesen klaren Rechtsgrundsatz hat die Vorinstanz verletzt, wenn sie die Schuldneranweisung einzig auf <ref-law> abgestützt hat.
Nach dem eingangs Gesagten hebt das Bundesgericht einen Entscheid aber erst dann auf, wenn nicht nur die Begründung, sondern auch das Ergebnis unhaltbar ist. Letzteres ist nicht der Fall, da die Schuldneranweisung vorliegend auf <ref-law> hätte gestützt werden können. Nach dieser Bestimmung kann das Gericht vorsorgliche Massnahmen auch dann anordnen, wenn die Ehe bereits aufgelöst ist, das Verfahren über Scheidungsfolgen aber fortdauert. Die Bestimmungen über den Schutz der ehelichen Gemeinschaft sind sinngemäss anwendbar, worunter insbesondere auch die Anweisung gemäss <ref-law> fällt (vgl. URS GLOOR, in: Basler Kommentar, Zivilgesetzbuch I, 3. Aufl. 2006, N. 10 zu <ref-law>).
4.4 Die Schuldneranweisung erweckt allerdings unter zwei anderen, miteinander zusammenhängenden Aspekten Bedenken. Es stellt sich nämlich die Frage, ob das Gemeinwesen als Zessionar überhaupt berechtigt ist, diese privilegierte Art der Zwangsvollstreckung anzubegehren, und des Weiteren, ob die Massnahme in diesem Fall einer Verhältnismässigkeitsprüfung standhält. Der Staat als Abtretungsgläubiger ist nämlich - im Unterschied zur Regelsituation des Unterhaltsberechtigten - keineswegs in besonders dringender oder existentieller Weise auf die Erfüllung der Unterhaltsschuld angewiesen, so dass ihm der übliche Betreibungsweg durchaus zumutbar wäre (vgl. SUHNER, a.a.O., S. 49; HAUSHEER UND ANDERE, a.a.O., N. 13b zu <ref-law>). Vorliegend kann die Frage allerdings nicht vertieft überprüft werden, da der Beschwerdeführer in dieser Hinsicht keine willkürliche Anwendung von <ref-law> gerügt hat.
4.5 Der Beschwerdeführer bringt schliesslich vor, <ref-law> sei insofern willkürlich angewendet worden, als die Schuldneranweisung in sein Existenzminimum eingreife. Zudem werde dadurch <ref-law> verletzt. Es sei völlig unhaltbar, von einem hypothetischen Einkommen in der Höhe von Fr. 12'000.-- auszugehen. Eine Schuldneranweisung müsse sich auf das tatsächlich erzielte Einkommen beziehen.
4.6 Gemäss konstanter und jüngst bestätigter bundesgerichtlicher Rechtsprechung ist dem Unterhaltsschuldner das betreibungsrechtliche Existenzminimum zu belassen (<ref-ruling> mit Hinweisen). Dies gilt auch in der Zwangsvollstreckung, soweit nicht der Unterhaltsberechtigte selbst, sondern ein Dritter wie das Gemeinwesen als Gläubiger auftritt (<ref-ruling> E. 3b. S. 102 mit Hinweisen). Ob das Kantonsgericht diesen Grundsätzen Rechnung getragen hat oder nicht, ist nachfolgend zu prüfen.
Entgegen den Ausführungen des Beschwerdeführers hat das Kantonsgericht nicht auf ein hypothetisches Einkommen, sondern auf eine Schätzung des effektiv erzielten Einkommens abgestellt. Diese Schätzung hat es dem Massnahmeentscheid des Bezirksgerichts Visp vom 13. Juni 2006 entnommen. Die Ausführungen des Beschwerdeführers über die Berücksichtigung hypothetischer Einkommen gehen damit an der Sache vorbei.
Hingegen hat der Beschwerdeführer der Vorinstanz zusammen mit seiner Gesuchsantwort eine Pfändungsurkunde des Betreibungsamts Visp vom 12. Januar 2009 eingereicht und sich auf diese denn auch sinngemäss berufen. Aus der Urkunde ergibt sich, dass der zuständige Pfändungsbeamte als pfändbare Gegenstände einzig ein monatliches Netto-Einkommen des Beschwerdeführers von Fr. 4'912.-- aufgefunden hat und die Pfändung zur Deckung der in Betreibung gesetzten Forderungen ungenügend ist.
Die Pfändungsurkunde stellt eine öffentliche Urkunde im Sinne von <ref-law> dar (<ref-ruling> E. 5b S. 16). Damit erbringt sie für die durch sie bezeugten Tatsachen vollen Beweis, solange nicht die Unrichtigkeit ihres Inhaltes nachgewiesen ist. Bei der Pfändungsurkunde gilt diese erhöhte Beweiskraft auch für die Liste der gepfändeten Gegenstände und zwar auch insofern, als der Pfändungsbeamte bei einer - wie vorliegend - ungenügenden Pfändung angibt, keine weiteren zur Pfändung geeigneten Objekte gefunden zu haben. Der Pfändungsbeamte kann zwar nur verurkunden, was er selber wahrgenommen hat, doch geniesst seine Feststellung insoweit ein erhöhtes Vertrauen, als er gehalten ist, allen Hinweisen auf weiteres pfändbares Vermögen und Einkommen nachzugehen (vgl. ANDRÉ E. LEBRECHT, in: Kommentar zum Bundesgesetz über Schuldbetreibung und Konkurs, SchKG II, 1998, N. 13 zu <ref-law>). Somit ist vorliegend grundsätzlich davon auszugehen, dass der Beschwerdeführer tatsächlich kein höheres Einkommen erzielt, als in der Pfändung festgestellt wurde.
Das Kantonsgericht hat die Pfändungsurkunde zwar hinsichtlich der darin aufgeführten Existenzminima beachtet, nicht aber im Hinblick auf das erzielte Einkommen. Stattdessen hat es pauschal auf die Einkommensschätzung des Bezirksgerichts Visp aus dem Jahre 2006 verwiesen. Damit hat es allerdings weder die Natur der Pfändungsurkunde beachtet noch hat es berücksichtigt, dass die Urkunde wesentlich jüngeren Datums ist als der erwähnte Massnahmeentscheid. Schliesslich hat es auch nicht bedacht, dass im Rahmen vorsorglicher Massnahmen während der Scheidung die Glaubhaftmachung der anspruchsbegründenden Tatsachen genügt (<ref-ruling> E. 3 S. 377). Eine bloss glaubhaft erscheinende Tatsache, zumal sie sich vorliegend in einer blossen Schätzung erschöpft, kann für sich allein noch keine Entkräftung der öffentlichen Urkunde bewirken (vgl. Hans Schmid, in: Basler Kommentar, Zivilgesetzbuch I, 3. Aufl. 2006, N. 30 zu <ref-law>). Dass die Vorinstanz vorliegend ohne weiteres auf eine blosse Einkommensschätzung abgestellt hat, erweist sich mithin als unhaltbar. In der Folge hat sie mit der Schuldneranweisung über den gesamten Nettolohn des Beschwerdeführers in krasser Weise in sein Existenzminimum eingegriffen.
4.7 Der Entscheid der Vorinstanz ist deshalb aufzuheben. Die Schuldneranweisung kann einzig in einem das Existenzminimum wahrenden Umfang aufrecht erhalten werden, d.h. entsprechend den vorinstanzlichen Anträgen des Beschwerdeführers im Betrag von Fr. 1'350.--. Sollte der Beschwerdeführer im vorliegenden Verfahren mit seinem diesbezüglich nicht restlos klaren Antrag eine weitergehende Aufhebung verlangen, so läge ein unzulässiges neues Begehren vor (<ref-law>). Angesichts seiner Beschwerdebegründung ist dies aber nicht anzunehmen.
5. Bei diesem Ausgang des Verfahrens trägt der Beschwerdegegner, welcher in seinen Vermögensinteressen betroffen ist, die Gerichtskosten des bundesgerichtlichen Verfahrens (<ref-law>). Entsprechend wird der vorinstanzliche Entscheid auch im Kostenpunkt aufgehoben und die Sache zur Neuverteilung der kantonalen Gerichtskosten an das Kantonsgericht zurückgewiesen. Zudem hat der Beschwerdegegner dem Beschwerdeführer eine Parteientschädigung sowohl für das bundesgerichtliche wie das vorinstanzliche Verfahren zu entrichten (<ref-law>). Die Parteientschädigung für das kantonale Verfahren ist durch die Vorinstanz festzusetzen (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird gutgeheissen und das Urteil des Kantonsgerichts Wallis vom 1. Oktober 2009 aufgehoben.
2. Die S._ AG wird angewiesen, den Lohn von X._, geb. xxxx 1954, im Umfang von Fr. 1'350.-- bis zum rechtskräftigen Urteil in der Scheidung X._ / Z._ auf das Postkonto Nr. xxxx des Kantons Waadt, Service de prévoyance et d'aide sociales, zu überweisen.
3. Im Übrigen wird die Sache zur Neuverteilung der kantonalen Gerichtskosten und zur Festlegung einer Parteientschädigung an das Kantonsgericht zurückgewiesen.
4. Die Gerichtskosten von Fr. 2'000.-- werden dem Beschwerdegegner auferlegt.
5. Der Beschwerdegegner hat den Beschwerdeführer für das bundesgerichtliche Verfahren mit Fr. 2'000.-- zu entschädigen.
6. Dieses Urteil wird den Parteien und dem Kantonsgericht Wallis schriftlich mitgeteilt.
Lausanne, 15. Februar 2010
Im Namen der II. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Der Gerichtsschreiber:
Hohl Zingg