Sachverhalt:
A. Z._ (geb. xxxx 1966) und X._ (geb. xxxx) sind die nicht miteinander verheirateten Eltern der gemeinsamen Tochter Y._ (geb. xxxx 2006).
Am 30. Mai 2006 unterzeichneten Z._ und X._ einen Unterhaltsvertrag. Darin vereinbarten sie für die Dauer der Hausgemeinschaft die gemeinsame Wahrnehmung der Erziehungsverantwortung und den gemeinsamen finanziellen Unterhalt für das Kind unter Berücksichtigung der Aufteilung der Betreuung. Für den Fall der Auflösung der Hausgemeinschaft vereinbarten sie im Wesentlichen, Y._ in alternierender Obhut zu betreuen; wenn immer möglich solle Y._ je zur Hälfte der Zeit von beiden Elternteilen betreut und erzogen werden. Die Vormundschaftsbehörde der Gemeinde Schwyz genehmigte diesen Vertrag am 25. August 2006.
Im September 2007 zog Z._ aus dem Einfamilienhaus von X._ aus und bezog in der gleichen Ortschaft eine Wohnung. Y._ lebte von da an abwechselnd bei der Mutter und beim Vater.
Am 22. Januar 2009 schlossen Z._ und X._ einen Vergleich. Dieser sah, soweit vorliegend relevant, im Wesentlichen vor, dass der Vater das Kind am ersten und dritten Wochenende eines jeden Monats von Donnerstag 10.00 Uhr bis Sonntag 19.00 Uhr betreut und jedes zweite und vierte Wochenende von Donnerstag 10.00 Uhr bis Samstag 10.00 Uhr sowie während sechs Ferienwochen pro Jahr. In der übrigen Zeit sei Y._ von der Mutter zu betreuen; jeweils am Mittwoch werde Y._ zudem in einer Kinderkrippe fremdbetreut.
Dieser Vergleich wurde vom Bezirksgericht Schwyz am 23. Januar 2009 sowie von der Vormundschaftsbehörde Schwyz am 17. April 2009 genehmigt.
Am 3. Dezember 2009 klagte Z._ beim Regierungsrat des Kantons Schwyz als vormundschaftliche Aufsichtsbehörde auf Zuteilung der elterlichen Sorge (einschliesslich einer Neuregelung des Besuchsrechts), heiratete am 4. Dezember 2009 ihren neuen Partner mit Wohnsitz im Liechtenstein, kündigte per Ende Januar 2010 ihre Anstellung als Psychomotorik-Therapeutin in B._ und verlegte ihren Wohnsitz im April 2010 zu ihrem Ehemann nach Liechtenstein.
Nach Einholung eines kinderpsychiatrischen Gutachtens vom 24. Juni 2011 beschloss der Regierungsrat des Kantons Schwyz am 17. August 2011, das Gesuch um Neuregelung der gemeinsamen elterlichen Sorge abzuweisen (Dispositiv-Ziff. 1), übertrug die Obhut auf den Vater (Dispositiv-Ziff. 2) und liess die geltende Betreuungsregelung bestehen bzw. ordnete für den Fall der Nichtumsetzbarkeit derselben an, dass die Mutter jedes zweite Wochenende von Freitag 17.00 Uhr bis Sonntagabend 19.00 Uhr mit Y._ verbringen könne zuzüglich sechs Wochen Ferien pro Jahr (Dispositiv-Ziff. 3).
B. Gegen diesen Beschluss erhob Z._ am 8. September 2011 Beschwerde an das Verwaltungsgericht des Kantons Schwyz und erneuerte im Wesentlichen ihre vor erster Instanz gestellten Anträge. Mit Entscheid vom 8. März 2012 hob das Verwaltungsgericht des Kantons Schwyz (soweit vorliegend relevant) die Ziffern 2 und 3 des angefochtenen Regierungsratsbeschlusses auf und übertrug die Obhut von Y._ nach dem Ende des laufenden Kindergartenjahres 2011/2012 (d.h. ab Anfang Juli 2012) auf die Mutter bzw. ordnete an, die weitere Einschulung habe an deren Wohnsitz im Liechtenstein zu erfolgen (Dispositiv-Ziff. 1.1); im Übrigen wies es die Beschwerde ab und liess insbesondere die gemeinsame elterliche Sorge bestehen (Dispositiv-Ziff. 1.2).
C. Mit Beschwerde in Zivilsachen vom 19. April 2012 gelangt X._ (nachfolgend: Beschwerdeführer) an das Bundesgericht und verlangt im Wesentlichen die Übertragung der Obhut an sich. Ausserdem sei die Betreuungsregelung vom 22. Januar 2009 (mit je hälftiger Obhut) beizubehalten. Sollte sie nicht umsetzbar sein, sei der Mutter jedes zweite Wochenende ein Besuchsrecht von Freitag 17.00 Uhr bis Sonntagabend 19.00 einzuräumen zuzüglich sechs Wochen Ferien pro Jahr. Zudem ersucht er um Gewährung der aufschiebenden Wirkung.
Am 8. Mai 2012 verfügte die Präsidentin der II. zivilrechtlichen Abteilung, der Beschwerde die aufschiebende Wirkung zuzuerkennen.
Es wurden die Akten, in der Sache selbst aber keine Vernehmlassungen eingeholt. Im Rahmen ihrer Stellungnahme zum Gesuch um aufschiebende Wirkung hat die Vorinstanz unaufgefordert gleichwohl zur Hauptsache Stellung genommen .

Erwägungen:
1. 1.1 Angefochten ist ein kantonal letztinstanzlicher Entscheid einer vormundschaftlichen Aufsichtsbehörde, der die Obhut eines Kindes unverheirateter Eltern bei bestehender gemeinsamer elterlicher Sorge neu regelt (<ref-law>), mithin ein öffentlich-rechtlicher Entscheid, der in unmittelbarem Zusammenhang mit Zivilrecht steht; die Beschwerde in Zivilsachen steht somit grundsätzlich offen (Art. 72 Abs. 2 lit. b Ziff. 5 bzw. Ziff. 7, Art. 75 Abs. 1 und Art. 90 BGG).
1.2 Das Bundesgericht prüft die Verletzung von Bundesrecht mit freier Kognition (<ref-law>). Dabei wendet es - im Rahmen der gestellten Anträge - das Recht von Amtes wegen an (<ref-law>; vgl. dazu <ref-ruling> E. 2.5 S. 262; <ref-ruling> E. 1.4 S. 140). Immerhin prüft das Bundesgericht - unter Berücksichtigung der allgemeinen Begründungspflicht der Beschwerde (Art. 42 Abs. 1 und 2 BGG) - grundsätzlich nur die geltend gemachten Rügen, es sei denn, die rechtlichen Mängel sind geradezu offensichtlich. Das Bundesgericht ist jedenfalls nicht gehalten, wie eine erstinstanzliche Behörde alle sich stellenden Rechtsfragen zu untersuchen, wenn diese vor Bundesgericht nicht (mehr) vorgetragen werden (<ref-ruling> E. 1.4.1 S. 254 mit Hinweisen).
Die Beschwerde ist dabei hinreichend zu begründen, andernfalls wird auf sie nicht eingetreten. In der Beschwerdeschrift ist in gedrängter Form darzulegen, inwiefern der angefochtene Entscheid Recht verletzt (<ref-law>). Dazu ist es unerlässlich, dass die Beschwerde auf die Begründung des angefochtenen Entscheids konkret eingeht und im Einzelnen aufzeigt, worin eine Rechtsverletzung liegt. Der Beschwerdeführer soll in der Beschwerdeschrift nicht bloss die Rechtsstandpunkte, die er im kantonalen Verfahren eingenommen hat, erneut bekräftigen, sondern mit seiner Kritik an den als rechtsfehlerhaft erachteten Erwägungen der Vorinstanz ansetzen (vgl. <ref-ruling> E. 2.1 S. 245 f.).
1.3 Das Bundesgericht ist an den festgestellten Sachverhalt grundsätzlich gebunden (<ref-law>). Diesbezüglich kann einzig vorgebracht werden, er sei offensichtlich unrichtig festgestellt worden (<ref-law>), wobei "offensichtlich unrichtig" mit "willkürlich" gleichzusetzen ist (Botschaft, BBl 2001 IV 4338; <ref-ruling> E. 1.2.2 S. 252; <ref-ruling> E. 7.1 S. 398), oder er beruhe auf einer anderen Rechtsverletzung im Sinn von <ref-law> (z.B. <ref-law> oder <ref-law>). Ausserdem muss in der Beschwerde aufgezeigt werden, inwiefern die Behebung der vorerwähnten Mängel für den Ausgang des Verfahrens entscheidend sein kann (<ref-law>; <ref-ruling> E. 2.2.2 S. 22). Für all diese Elemente gilt das strenge Rügeprinzip (<ref-law>; <ref-ruling> E. 1.4.2 S. 255). Das bedeutet, dass das Bundesgericht nur klar und detailliert erhobene und soweit möglich belegte Rügen prüft, während es auf ungenügend begründete Rügen und rein appellatorische Kritik am angefochtenen Entscheid nicht eintritt. Wird die Verletzung des Willkürverbots gerügt, reicht es sodann nicht aus, die Lage aus Sicht des Beschwerdeführers darzulegen und den davon abweichenden angefochtenen Entscheid als willkürlich zu bezeichnen; vielmehr ist im Einzelnen darzulegen, inwiefern das kantonale Gericht willkürlich entschieden haben soll und der angefochtene Entscheid deshalb an einem qualifizierten und offensichtlichen Mangel leidet (<ref-ruling> E. 2.2 S. 246).
2. Strittig ist vorliegend einzig die Obhutszuteilung, nicht aber die Beibehaltung des gemeinsamen elterlichen Sorgerechts.
2.1 Haben unverheiratete Eltern das gemeinsame Sorgerecht über ihr gemeinsames Kind inne, kann die Vormundschaftsbehörde - auf Begehren eines Elternteils, des Kindes oder von Amtes wegen - die Zuteilung des Sorgerechts neu regeln, wenn dies wegen wesentlicher Veränderung der Verhältnisse zum Wohl des Kindes geboten ist (<ref-law>). Diese Grundsätze gelten auch für eine Neuregelung der Obhut (als Teilgehalt der elterlichen Sorge). Für die Zuteilung der Obhut an einen Elternteil gelten grundsätzlich die gleichen Kriterien wie im Scheidungsfall.
Nach der Rechtsprechung hat das Wohl des Kindes Vorrang vor allen anderen Überlegungen, insbesondere vor den Wünschen der Eltern (zuletzt: Urteil 5A_157/2012 vom 23. Juli 2012 E. 3.1). Vorab muss die Erziehungsfähigkeit der Eltern geklärt werden. Ist diese bei beiden Elternteilen gegeben, sind vor allem Kleinkinder und grundschulpflichtige Kinder demjenigen Elternteil zuzuteilen, der die Möglichkeit hat und dazu bereit ist, sie persönlich zu betreuen. Erfüllen beide Elternteile diese Voraussetzung ungefähr in gleicher Weise, kann die Stabilität der örtlichen und familiären Verhältnisse ausschlaggebend sein. Unter Umständen kann die Möglichkeit der persönlichen Betreuung auch dahinter zurücktreten (Urteil 5C.212/2005 vom 25. Januar 2006 E. 4.2 und 4.4.1, in: FamPra.ch 2006 S. 753 ff.). Schliesslich ist - je nach Alter der Kinder - ihrem eindeutigen Wunsch Rechnung zu tragen. Diesen Kriterien lassen sich die weiteren Gesichtspunkte zuordnen, namentlich die Bereitschaft eines Elternteils, mit dem anderen in Kinderbelangen zusammenzuarbeiten oder die Forderung, dass eine Zuteilung der Obhut von einer persönlichen Bindung und echter Zuneigung getragen sein sollte (vgl. <ref-ruling> E. 4a S. 209; <ref-ruling> E. 2 und 3 S. 319 ff.; <ref-ruling> E. 3 S. 354 f.; <ref-ruling> E. 5.3 S. 180 f.).
Bei der Beurteilung der für die Obhutszuteilung massgebenden Kriterien verfügt das Sachgericht über ein weites Ermessen (vgl. alle soeben zitierten Urteile). Auf Beschwerde greift das Bundesgericht deshalb nur ein, wenn das Sachgericht grundlos von in Rechtsprechung und Lehre anerkannten Grundsätzen abgewichen ist, wenn es Gesichtspunkte berücksichtigt hat, die keine Rolle hätten spielen dürfen, oder wenn es umgekehrt rechtserhebliche Umstände ausser Acht gelassen hat. Der Ermessensentscheid muss sich als im Ergebnis offensichtlich unbillig, als in stossender Weise ungerecht erweisen (BGE 109 la 107 E. 2c S. 109; <ref-ruling> E. 3 S. 355; <ref-ruling> E. 4b S. 6 f.; <ref-ruling> E. 1 S. 99).
2.2 Die Vorinstanz erwog im Wesentlichen Folgendes:
Die seit September 2007 getrennt lebenden Eltern hätten ihre Tochter zunächst gemäss dem sog. Pendelmodell betreut. Da die Mutter seit Ende November 2011 in Schwyz über keine Mietwohnung mehr verfüge, im Fürstentum Liechtenstein wohne und die Einschulung von Y._ absehbar werde, erweise es sich - im Sinne einer erwünschten Konstanz und Kontinuität - als unumgänglich, der Lebensmittelpunkt von Y._ auf einen Wohnort zu beschränken. Auch das eingeholte Gutachten spreche sich mit Nachdruck für eine solche Lösung aus. Werde die Obhut der Mutter zugeteilt, was sich vorliegend aufdränge (dazu sogleich), sei mit einer "Entkrampfung" des Elternverhältnisses zu rechnen, weshalb sich vorliegend die Aufrechterhaltung der gemeinsamen Sorge rechtfertige.
Mit Blick auf die Obhutsfrage schloss sich die Vorinstanz - nach einer umfassenden Prüfung der Situation - der gutachterlichen Empfehlung an, diese der Mutter zuzuteilen. Die vorinstanzliche Gesamtwürdigung umfasst im Wesentlichen die folgenden Gesichtspunkte: Dass Y._ zu Schwyz bereits einen gewissen Bezug habe, stehe einer Obhutszuteilung an die Mutter nicht entgegen, da für Y._ aufgrund ihres Alters primär ihre Bezugsperson im Vordergrund stehe und nicht ein bestimmter Ort. Ferner lebe der Beschwerdeführer in einem "Junggesellenhaushalt", wobei seine Freundin im Kanton Bern wohne und arbeite, während die Mutter mit ihrem neuen Ehemann zusammenlebe, was für Y._ vorteilhafter sei. Der Vater gehe ausserdem - nebst seiner Büroarbeit - in der gesamten Deutschschweiz auf Kundenbesuch und müsse sich öfters in dem von ihm verpachteten Restaurations- und Ferienhüttenbetrieb aufhalten, was als Aufenthaltsort für ein sechsjähriges Kind nicht adäquat sei; demgegenüber sei die Mutter mit einem Pensum von 20-30% erwerbstätig. Obschon auch bezüglich des Verhaltens der Mutter Verbesserungspotenzial bestehe, sei der Vater im Falle einer Obhutszuteilung voraussichtlich nicht bereit, Y._ uneingeschränkten Zugang zur Mutter zu gewähren. Bezüglich des logopädischen bzw. motorischen Behandlungsbedarfs von Y._ sei die Mutter zudem sensibilisierter und aufmerksamer, zumal sie von Beruf Psychomotorik-Therapeutin sei.
3. Der Beschwerdeführer wirft der Vorinstanz zunächst eine Verletzung von kantonalem Verwaltungsverfahrensrecht vor. Obwohl im vorliegenden Verfahren der Untersuchungsgrundsatz gelte, habe sich das Verwaltungsgericht in Verletzung von § 55 der Verordnung über die Verwaltungsrechtspflege vom 6. Juni 1974 nicht auf die Prüfung des Ermessensmissbrauchs bzw. der Ermessensüberschreitung beschränkt.
Es trifft zu, dass das Verwaltungsgericht nach dem anwendbaren § 55 der Verordnung über die Verwaltungsrechtspflege den regierungsrätlichen Ermessensentscheid nur auf Ermessensmissbrauch bzw. -überschreitung hätte prüfen dürfen.
Das Verwaltungsgericht hat aber festgestellt, dass die Frage des Kindeswohls stets im Hinblick auf die aktuellen Verhältnisse zu beantworten sei (E. 3.4.2) und dass sich die Verhältnisse im Vergleich zum Zeitpunkt der regierungsrätlichen Beschlussfassung geändert hätten (E. 3.4.3). Der Beschwerdeführer widerspricht keiner der beiden Erwägungen.
Sodann führt das Verwaltungsgericht an, in Kinderbelangen gelte die Untersuchungsmaxime (E. 3.5.1), was der Beschwerdeführer insofern bestätigt, als er selber mehrfach die Verletzung derselben geltend macht. In der Tat gelten in allen Kinderbelangen vor allen kantonalen Instanzen von Bundesrechts wegen die Offizial- und die Untersuchungsmaxime (BGE <ref-ruling>11 E. 3 S. 412; <ref-ruling> E. 2.a/bb S. 302; <ref-ruling> E. 3d S. 408). Gerade die Untersuchungsmaxime führt dazu, dass die mit der Sache befasste Instanz neue Umstände berücksichtigen muss (<ref-ruling> E. 5.2.1 S. 95; Urteil 5A_591/2008 vom 24. Oktober 2008 E. 3.2 und Urteil 5A_721/2011 vom 4. Januar 2012 E. 2.5). Insofern das kantonale Prozessrecht in Kinderbelangen die Berücksichtigung neuer Tatsachen verbietet, steht es im Widerspruch zum Bundesrecht und bleibt daher unbeachtlich. Daraus folgt ohne weiteres, dass bei Vorliegen neuer Tatsachen, die Überprüfungsbefugnis der Vorinstanz nicht auf Ermessensmissbrauch bzw. -überschreitung beschränkt sein konnte. Die Rüge erweist sich als unbegründet.
4. Unter dem Titel "unrichtige Feststellung des Sachverhalts" erhebt der Beschwerdeführer zahlreiche Rügen. Zum Teil handelt es sich tatsächlich um Sachverhaltsfragen und solche der Beweiswürdigung (s. dazu E. 4.1 bis 4.4 sogleich); teilweise macht er indes Rechtsfehler (Verletzung des Untersuchungsgrundsatzes; falsche Gewichtung von Zuteilungskriterien, Anwendung unzulässiger Zuteilungskriterien) geltend; diese Rügen werden in den E. 5 und 6 hiernach beurteilt.
4.1 Eine Sachverhaltsfeststellung ist willkürlich, wenn sie offensichtlich unhaltbar ist, zur tatsächlichen Situation in klarem Widerspruch steht oder auf einem offenkundigen Versehen beruht (<ref-ruling> E. 3.1 S. 178). Willkür in der Beweiswürdigung liegt vor, wenn das Gericht Sinn und Tragweite eines Beweismittels offensichtlich verkannt hat, wenn es ohne sachlichen Grund ein wichtiges Beweismittel, das für den Entscheid wesentlich sein könnte, unberücksichtigt gelassen hat oder wenn es auf Grundlage der festgestellten Tatsachen unhaltbare Schlussfolgerungen getroffen hat (<ref-ruling> E. 2.1 S. 9). Dass die Ergebnisse des Beweisverfahrens auch Schlüsse gestatten, die nicht mit den vom Sachgericht gezogenen übereinstimmen, bedeutet hingegen nicht schon Willkür (<ref-ruling> E. 2b S. 88). Es obliegt gemäss <ref-law> dem Beschwerdeführer, Willkür klar und detailliert und, soweit möglich, belegt zu rügen und im Einzelnen darzulegen, inwiefern die Beweiswürdigung an einem qualifizierten und offensichtlichen Mangel leidet (<ref-ruling> E. 1.3 S. 261 f.). Sodann muss er aufzeigen, inwiefern die Behebung desselben für den Ausgang des Verfahrens entscheidend sein kann (<ref-law>; <ref-ruling> E. 2.2.2 S. 22).
4.2 Zunächst rügt der Beschwerdeführer, dass die Vorinstanz auf seine Vernehmlassung vom 30. September 2011 abgestellt und daraus den Schluss gezogen habe, es sei unglaubwürdig, dass er bereit sei, der Tochter uneingeschränkten Zugang zur Mutter zu gewähren und es könne nicht angenommen werden, er sei bestrebt, Y._ nicht einem Loyalitätskonflikt auszusetzen (E. 5.5.2 des angefochtenen Entscheids). Es sei nämlich gerichtsnotorisch, dass "die Tochter-Verlust-Angst für den Kindsvater emotional höchst belastend sei", weshalb seinen Äusserungen nicht die Beachtung hätte zukommen dürfen, welche das Verwaltungsgericht ihnen zugemessen hat. Der Sache nach rügt der Beschwerdeführer Willkür in der Beweiswürdigung.
Dem Gericht unterbreitete abschätzige Äusserungen betreffend den anderen Elternteil lassen sich nicht mit angeblichen Verlustängsten rechtfertigen. Die Vorinstanz durfte auf die in der Vernehmlassung vom 30. September 2011 enthaltenen Ausführungen abstellen und die darin zum Ausdruck gebrachte Einstellung des Beschwerdeführers entsprechend würdigen.
4.3 Im Zusammenhang mit der vorinstanzlichen Feststellung, wonach vernünftig klingende Absprachen bezüglich Betreuungszeiten "offenbar nicht möglich" gewesen seien (E. 5.5.3 des angefochtenen Entscheids), wendet der Beschwerdeführer sodann ein, die Vorinstanz treffe Annahmen, ohne sich je vergewissert zu haben, was tatsächlich vorgefallen sei (S. 8 der Beschwerde). Dabei übergeht er mit Stillschweigen, dass das Verwaltungsgericht ausdrücklich auf zwei Aktenstellen verweist, und er behauptet nicht etwa, aus den fraglichen Akten lasse sich die gezogene Schlussfolgerung nicht ziehen. Auch diese Sachverhaltsrüge ist unbegründet.
5. Ausserdem rügt der Beschwerdeführer in zweifacher Hinsicht eine Verletzung des Untersuchungsgrundsatzes.
5.1 Wie bereits ausgeführt, gilt in Kinderbelangen uneingeschränkt der Untersuchungsgrundsatz (vgl. E. 3). Letzterer verpflichtet den Richter, von sich aus alle Elemente in Betracht zu ziehen, die entscheidwesentlich sind, und unabhängig von den Anträgen der Parteien Beweise zu erheben. Diese Pflicht ist indes nicht ohne Grenzen und entbindet die Parteien nicht von einer aktiven Mitwirkung am Verfahren, indem sie Hinweise zum Sachverhalt machen oder Beweise bezeichnen (dazu BGE <ref-ruling>11 E. 3.2.1 und 3.2.2 S. 412 ff.; zuletzt: 5A_775/2011 vom 8. März 2012 E. 2.1.3).
Wer sich auf die Untersuchungsmaxime beruft bzw. eine Verletzung derselben geltend macht, muss daher zunächst aufzeigen, dass das Gericht den Sachverhalt unvollständig und damit willkürlich festgestellt hat. Sodann muss der Beschwerdeführer diejenigen Tatsachen behaupten, die das Gericht festzustellen bzw. abzuklären unterlassen hat. Schliesslich obliegt es ihm darzutun, inwiefern die behaupteten Tatsachen für den Ausgang des Verfahrens entscheidend sind (s. dazu Urteil 5A_299/2012 vom 2012 E. 3.4).
5.2 Diesen Begründungsanforderungen kommt der Beschwerdeführer nicht nach.
5.2.1 Zunächst hält der Beschwerdeführer der Vorinstanz vor, erwogen zu haben, bei einer Zuteilung der Obhut an die Beschwerdegegnerin werde die Tochter unter der Woche in einem Haushalt mit weiblicher und männlicher Bezugsperson aufwachsen, während der Beschwerdeführer unter der Woche alleine lebe und die Tochter somit in einem Junggesellenhaushalt aufwachsen würde (E. 5.2 des angefochtenen Entscheids), und zwar ohne abgeklärt zu haben, ob der Ehemann der Beschwerdegegnerin unter der Woche auch tatsächlich im gemeinsamen Haushalt lebt und Y._ mit einer männlichen Bezugsperson aufwachsen kann (S. 7 und S. 11 der Beschwerde). Indes behauptet der Beschwerdeführer nicht, der Ehemann der Beschwerdegegnerin verbringe die Wochentage nicht im Liechtenstein, noch zeigt er auf, dass diese Sachverhaltselemente letztlich ausschlaggebend waren für die Zuteilung der Obhut an die Beschwerdegegnerin, bzw. dass, falls der Ehemann tatsächlich nur die Wochenenden im gemeinsamen Haushalt verbringen würde, die Obhut dem Beschwerdeführer hätte übertragen werden müssen. Überdies ergeben sich auch aus den Akten keinerlei Anhaltspunkte dafür, dass der Ehemann der Beschwerdegegnerin seine arbeitsfreie Zeit ausserhalb des gemeinsamen Haushalts verbringt, und auch der Beschwerdeführer behauptet dies nicht. Vor diesem Hintergrund hatte das Verwaltungsgericht keine Veranlassung, diesbezüglich weitere Abklärungen vorzunehmen.
5.2.2 Ferner wendet der Beschwerdeführer ein, die Vorinstanz sei davon ausgegangen, er müsse regelmässig seinen verpachteten Restaurations- und Ferienhüttenbetrieb in C._ aufsuchen (wobei ein solcher Aufenthaltsort, sollte er regelmässig anfallen, für ein 6-jähriges Kind kaum als adäquat zu beurteilen wäre; E. 5.3 des angefochtenen Entscheids), ohne darüber Beweis geführt zu haben, wie viel Zeit die Betreuung der verpachteten Restaurationsbetriebe in Anspruch nehme. Er habe Zeugen offeriert, um seine Betreuungskapazität und -intensität zu belegen (S. 8 der Beschwerde). Auch hier behauptet der Beschwerdeführer nicht und legt nicht dar, wie viel (bzw. wie wenig) Zeit er tatsächlich aufwendet, um sich um die fraglichen Restaurationsbetriebe zu kümmern. Ebenso wenig führt er aus, wie (bzw. wie wenig) sich diese Aufgaben auf seine eigene Betreuungskapazität auswirken würden; die Behauptung, Zeugen könnten dies bestätigen, genügt nicht, wenn unklar bleibt, was genau diese Zeugen bestätigen könnten.
5.2.3 Den in diesem Zusammenhang jeweils gleichzeitig erhobenen, aber nicht selbständig begründeten Sachverhalts- und Gehörsrügen kommt keine eigenständige Bedeutung zu; darauf ist nicht einzutreten.
6. 6.1 Sodann wirft der Beschwerdeführer der Vorinstanz vor, offensichtlich und willkürlich verkannt zu haben, dass Y._ "seit ihrer Geburt in Schwyz eingebettet" sei und mit einem "überdurchschnittlich grossen Kreis von Familienangehörigen und Freunden des Kindesvaters" Kontakt habe (S. 7 der Beschwerde). Vom Umfeld des Kindes in Liechtenstein wisse die Vorinstanz eben so wenig wie er selbst: Die Vorinstanz erwähne denn auch nur den dortigen Kindergarten.
Mit Blick auf das Alter von Y._ hat die Vorinstanz festgehalten, die Stabilität der Verhältnisse hänge in erster Linie von den Bezugspersonen ab und nicht von den örtlichen Verhältnissen, weshalb letzterem Kriterium vorliegend eine untergeordnete Bedeutung zukomme (E. 5.1 des angefochtenen Entscheids). Daraus ergibt sich zunächst einmal, dass das Verwaltungsgericht die räumliche Verwurzelung der Tochter und damit das Kriterium der örtlichen Stabilität sehr wohl in seine Beurteilung einbezogen, aber demjenigen der persönlichen Stabilität mehr Gewicht beigemessen hat. Der Beschwerdeführer legt nicht dar, inwiefern das Verwaltungsgericht mit dieser Gewichtung das ihm zustehende Ermessen überschritten haben soll. Die Rüge ist unbegründet.
6.2 Der Beschwerdeführer führt zudem ins Feld, er verfüge im Gegensatz zur Kindsmutter über keinen "Ernährer qua Heirat". Daraus einen Obhuts-Vorteil der Kindsmutter abzuleiten, sei verfassungsrechtlich "mehr als verwegen und realitätsfremd". Was der Beschwerdeführer der Vorinstanz unterstellt, hat diese gar nicht gesagt. Darauf ist nicht einzutreten.
6.3 Ferner wendet der Beschwerdeführer ein, die Gutachter attestierten ihm die zur Obhut des Kindes notwendigen Eigenschaften. Wenn die Vorinstanz folgere, die "Psychomotorik-Therapeutin-Kindsmutter" sei eher zur Obhut geeignet, so sei dies aktenwidrig und zudem diskriminiere die Vorinstanz damit den Kindsvater, was eine ganz klare Rechtsverletzung und Willkür sei.
Insofern der Beschwerdeführer hier eine Sachverhaltsrüge vorträgt (Einwand der Aktenwidrigkeit), kommt er seiner Begründungspflicht nicht nach (s. dazu E. 1.3), zumal nicht ersichtlich ist, welche Sachverhaltsfeststellung er überhaupt meint; darauf ist nicht einzutreten.
Das Verwaltungsgericht hat - nebst zahlreichen anderen Faktoren - die berufliche Qualifikation der Beschwerdegegnerin als Psychomotorik-Therapeutin in ihre Erwägungen einbezogen. Dieses Kriterium war deshalb relevant, weil die behandelnde Logopädin ausgeführt hatte, Y._ "hinke" in Sachen Motorik "hintendrein". Darauf hat der Beschwerdeführer selbst hingewiesen (E. 5.7 des angefochtenen Entscheids). Wenn nun das Verwaltungsgericht daraus folgert, die Ausbildung der Kindsmutter spreche daher eher für eine Obhut bei ihr, ist kein Ermessensmissbrauch und damit keine Rechtsverletzung ersichtlich.
Ebenso wenig ist darin eine Diskriminierung des Kindsvaters zu erkennen, denn die Attestierung der Erziehungsfähigkeit des Vaters genügt für sich alleine nicht, um die Obhutsfrage zu beantworten (s. dazu E. 2.1)
6.4 Ausserdem wirft der Beschwerdeführer dem Verwaltungsgericht vor, auf das Gutachten der Ambulanten Psychiatrischen Dienste (APD) des Kantons Zug abgestellt zu haben, obwohl die Gutachter sich nicht vom Wohl des Kindes, sondern von demjenigen der Kindsmutter hätten leiten lassen. So hätten diese eine Empfehlung zur Einschulung der Tochter im Liechtenstein abgegeben, weil der Kindsmutter nicht zugemutet werden könne, an mehreren Tagen pro Woche in der Region Schwyz zu leben.
Der Beschwerdeführer gibt die fraglichen Ausführungen im Gutachten verkürzt wieder. Dort wird nämlich nicht nur festgehalten, dass es die Mutter nach dem Vorgefallenen zu sehr belasten würde, mehrere Tage pro Woche in Schwyz zu wohnen, sondern auch, dass sich diese Belastung negativ auf das Kind auswirken würde (Gutachten S. 29 oben). Damit haben die Gutachter das Kindeswohl nicht nur nicht unterschlagen, sondern explizit berücksichtigt. Der hier erhobene Vorwurf trifft mithin nicht zu. Nachdem der Beschwerdeführer keine weiteren Einwendungen gegen die Vollständigkeit, die Nachvollziehbarkeit oder die Schlüssigkeit des Gutachtens erhebt, durfte das Verwaltungsgericht im Rahmen der ihm obliegenden freien Beweiswürdigung darauf abstellen (allgemein: <ref-ruling> E. 4.2.3 S. 391; <ref-ruling> E. 4.4.1 S. 269, je mit Hinweisen).
Den in diesem Zusammenhang erhobenen Rügen der Verletzung des Untersuchungsgrundsatzes und der Begründungspflicht kommt keine selbständige Bedeutung zu; darauf ist nicht einzutreten.
6.5 Unter Hinweis auf das Bundesgerichtsurteil 5A_170/2009 vom 10. Juni 2009 macht der Beschwerdeführer sodann geltend, auch im Zusammenhang mit der Obhutszuteilung müsse gelten, dass eine Änderung der bisherigen Regelung nur dann gerechtfertigt sei, wenn die Grundbedingungen für eine gemeinsame Verantwortung nicht mehr gegeben seien. Vorliegendenfalls habe die Beschwerdegegnerin ohne Not und ohne Absprache mit dem Beschwerdeführer ihren Wohnsitz wie auch denjenigen der Tochter verlegt und ihre Wohnung in Schwyz aufgegeben. Dies könne niemals ausreichend Grund sein, die Vereinbarung betreffend die gemeinsame elterliche Sorge und Obhut aufzuheben und in Anwendung von <ref-law> neu zu regeln.
Dem Beschwerdeführer ist insofern zuzustimmen, als eine Vereinbarung über die elterliche Sorge und Obhut nicht einseitig aufgekündigt werden kann. Wie indes bereits dargelegt, ist die Obhut neu zu regeln, wenn dies wegen wesentlicher Veränderung der Verhältnisse zum Wohl des Kindes geboten ist (E. 2.1). Ob sich die Verhältnisse geändert haben, ist nach objektiven Kriterien zu beurteilen. Grundsätzlich bleiben die Gründe, welche zu den veränderten Verhältnissen geführt haben, unbeachtlich; vorbehalten bleibt einzig der offenbare Rechtsmissbrauch. Einen solchen macht der Beschwerdeführer - zu Recht - nicht geltend; ebenso wenig bestreitet er, dass sich die Verhältnisse (Wegzug der Mutter nach Liechtenstein, Aufnahme einer Erwerbstätigkeit in Liechtenstein, Erreichen des Kindergartenalters der Tochter) tatsächlich geändert haben. Nach dem Gesagten ist nicht entscheidend, dass die Beschwerdegegnerin die Gründe für die Veränderung der Verhältnisse gesetzt hat; massgebend ist das Wohl des Kindes. Dass Letzterem am besten gedient ist, wenn die Tochter in die alleinige Obhut der Mutter gestellt wird, vermag der Beschwerdeführer - wie in den vorstehenden Erwägungen dargetan - nicht zu widerlegen.
6.6 Schliesslich wirft der Beschwerdeführer der Vorinstanz die Verletzung einer ganzen Reihe verfassungs- bzw. völkerrechtlicher Normen vor (Art. 8, Art. 9, Art. 11, Art. 14 und Art. 41 BV; Art. 8 EMRK; Art. 3, Art. 7, Art. 9 und Art. 18 UNKRK). Diesen Bestimmungen kommt indes keine über <ref-law> hinausgehende Bedeutung zu, was der Beschwerdeführer im Übrigen auch nicht darlegt (vgl. <ref-ruling> E. 3.4 S. 587). Auf diese, teilweise auf einigermassen abenteuerlichen Überlegungen basierenden Rügen ist nicht einzutreten.
7. Zusammenfassend ist die Obhutszuteilung nicht zu beanstanden. Hinsichtlich der Regelung des Besuchsrechts erhebt der Beschwerdeführer keine selbständigen Rügen. Ebenso wenig begründet er, ob bzw. weshalb er die vorinstanzliche Kostenregelung unabhängig vom Ausgang des bundesgerichtlichen Verfahrens anficht (vgl. Rechtsbegehren Ziff. 3). Darauf ist daher nicht weiter einzugehen.
Damit wird die Umteilung der Obhut über das Kind Y._ an die Beschwerdegegnerin bzw. dessen Einschulung in den Kindergarten im Liechtenstein definitiv und muss vollstreckt werden. Da der in der vorinstanzlichen Urteilsziffer 1.1 im Hinblick auf die Vollstreckung angeordnete Termin ("anfangs Juli 2012") inzwischen abgelaufen ist, wird er auf den Beginn der Herbstschulferien in Schwyz (1. Oktober 2012) neu angesetzt. Hinsichtlich persönlichem Verkehr und Betreuung von Y._ gelten bis zu diesem Zeitpunkt weiterhin die im Zwischenbescheid des Verwaltungsgerichts des Kantons Schwyz vom 21. Dezember 2011 getroffenen Anordnungen, es sei denn die Eltern treffen einvernehmlich eine andere Regelung.
8. Nach dem Gesagten ist die Beschwerde abzuweisen, soweit darauf eingetreten werden kann.
Die Gerichtskosten sind dem Beschwerdeführer aufzuerlegen (<ref-law>). Der Gegenseite ist kein entschädigungspflichtiger Aufwand entstanden.

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit darauf eingetreten werden kann.
Die Obhut über das Kind Y._ wird ab dem 1. Oktober 2012 auf die Kindsmutter übertragen. Bis zu diesem Zeitpunkt gilt weiterhin die Betreuungsregelung gemäss dem Zwischenbescheid des Verwaltungsgerichts des Kantons Schwyz vom 21. Dezember 2011.
2. Die Gerichtskosten von Fr. 2'000.-- werden dem Beschwerdeführer auferlegt.
3. Es werden keine Parteientschädigungen zugesprochen.
4. Dieses Urteil wird den Parteien und dem Verwaltungsgericht des Kantons Schwyz, Kammer III, schriftlich mitgeteilt.
Lausanne, 10. September 2012
Im Namen der II. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Hohl
Der Gerichtsschreiber: Schwander