Sachverhalt:
A. X._ (geb. 1973, britischer Staatsangehöriger) und Z._ (geb. 1979, deutsche Staatsangehörige) sind die nicht miteinander verheirateten Eltern der Kinder S._ (geb. 2005) und T._ (geb. 2007). Die Eltern trennten sich im August 2009, seither leben die Kinder hauptsächlich bei der Mutter. Für die in Deutschland geborene S._ besteht eine gemeinsame elterliche Sorge, für T._ liegt die alleinige elterliche Sorge bei der Mutter. Sowohl der Vater als auch die Mutter haben inzwischen geheiratet.
B. Die Sozialkommission A._ vertraute mit Beschluss vom 7. Juni 2010 die Obhut über beide Kinder der Mutter an und regelte das Besuchsrecht des Vaters. Gestützt auf einen Abklärungsbericht des Jugendsekretariates des Bezirks Meilen errichtete die Sozialkommission am 25. Oktober 2010 für beide Kinder eine Beistandschaft gemäss Art. 308 Abs. 1 und 2 ZGB. Infolge Umzugs der Parteien kam es daraufhin zu einem Zuständigkeitswechsel an die Vormundschaftsbehörde B._. Diese bezeichnete am 25. Januar 2011 Y._ als Beistand. Mit Beschluss vom 12. Juli 2011 regelte die Vormundschaftsbehörde den persönlichen Verkehr neu. Insbesondere reduzierte sie das 14-tägige Besuchswochenende von bisher Donnerstagabend bis Montagmorgen auf Freitag, 18:00 Uhr, bis Sonntag, 18:00 Uhr. Sie setzte das Ferienrecht des Vaters auf sechs Wochen fest und regelte die Besuchszeiten an den Fest- und Feiertagen sowie diverse Modalitäten für die Ausübung der Rechte.
C. Gegen diesen Entscheid erhob der Vater Beschwerde an den Bezirksrat Uster. Er beantragte insbesondere, die Besuchswochenenden seien wieder auf Donnerstag bis Montag auszudehnen. Der Bezirksrat sistierte das Verfahren bis zum Vorliegen eines von der Vormundschaftsbehörde in Auftrag gegebenen Abklärungsberichts von Dr. phil. U._ und nahm das Verfahren nach Eingang des Gutachtens wieder auf. Mit Replik vom 16. Januar 2012 und Nachtrag zur Replik vom 27. Januar 2012 ergänzte der Vater seine Rechtsbegehren und stellte neue Anträge (Ernennung eines neuen Beistandes; Anweisung an die Eltern, Mediationsgespräche zu besuchen; Anordnung, den anderen Elternteil beizuziehen, bevor die Kinder über Nacht in die Obhut einer Drittperson gegeben werden; zusätzliche Übernachtung unter der Woche und Besuchsrecht an Geburtstagen). Der Bezirksrat Uster hiess die Beschwerde am 23. Juli 2012 teilweise gut. Auf die in der Replik und im Nachtrag zur Replik gestellten Anträge trat der Bezirksrat nicht ein und im Übrigen wies er die Beschwerde ab.
D. Der Vater erhob am 23. Juli 2012 Berufung an das Obergericht des Kantons Zürich. Er stellte im Wesentlichen dieselben Anträge wie vor dem Bezirksrat Uster. Die Mutter reichte keine Berufungsantwort ein. Unaufgefordert legte der Vater am 23. November 2012 einen Nachtrag zur Beschwerde vor. Im Entscheid vom 28. November 2012 wies das Obergericht die Berufung ab, soweit es darauf eintrat.
E. Mit Eingabe vom 15. Januar 2013 hat X._ (nachfolgend Beschwerdeführer) beim Bundesgericht Beschwerde erhoben. Er beantragt erneut die Ausdehnung seiner Kontaktrechte, wobei auf die einzelnen Anträge im Sachzusammenhang einzugehen sein wird.
Das Bundesgericht hat die Akten, in der Sache selbst aber keine Vernehmlassungen eingeholt.

Erwägungen:
1. Angefochten ist ein kantonal letztinstanzlicher Entscheid (Art. 75 Abs. 1 BGG), der den persönlichen Verkehr zwischen dem Beschwerdeführer und seinen Kindern regelt (Art. 273 ZGB). Dieser unterliegt der Beschwerde in Zivilsachen (Art. 72 Abs. 2 lit. b Ziff. 6 BGG) und ist nicht vermögensrechtlicher Natur (Art. 74 BGG; Urteil 5A_830/2010 vom 30. März 2011 E. 1.1). Der Beschwerdeführer ist nach Art. 76 Abs. 1 BGG zur Beschwerde berechtigt. Die Beschwerdefrist gemäss Art. 100 Abs. 1 BGG ist eingehalten. Auf die Beschwerde ist somit einzutreten.
2. Das Bundesgericht ist an den von den kantonalen Instanzen festgestellten Sachverhalt gebunden (Art. 105 Abs. 1 BGG). Diesbezüglich kann einzig vorgebracht werden, der Sachverhalt sei offensichtlich unrichtig festgestellt worden (Art. 97 Abs. 1 BGG).
In rechtlicher Hinsicht hat das Bundesgericht freie Kognition (Art. 106 Abs. 1 BGG). Indes kommt den kantonalen Behörden bei der Regelung und Ausgestaltung des persönlichen Verkehrs Ermessen zu. Das Bundesgericht übt eine gewisse Zurückhaltung in der Überprüfung solcher Urteile (<ref-ruling> E. 3. S. 210; <ref-ruling> E. 4a S. 235). Es greift nur ein, wenn die kantonale Instanz von dem ihr zustehenden Ermessen falschen Gebrauch gemacht hat, das heisst, wenn sie grundlos von in Lehre und Rechtsprechung anerkannten Grundsätzen abgegangen ist, wenn sie Gesichtspunkte berücksichtigt hat, die keine Rolle hätten spielen dürfen, oder wenn sie umgekehrt rechtserhebliche Umstände ausser Acht gelassen hat. Aufzuheben und zu korrigieren sind ausserdem Ermessensentscheide, die sich als im Ergebnis offensichtlich unbillig, als in stossender Weise ungerecht erweisen (<ref-ruling> E. 2 S. 123 f.; <ref-ruling> E. 1 S. 99).
3. Der Beschwerdeführer rügt eine Verletzung von Art. 311 Abs. 1 ZPO, soweit die Vorinstanz auf seine Berufung nicht eingetreten ist (betroffene Anträge: zusätzliche Übernachtung unter der Woche sowie die als "alternative Betreuungsvariante" bezeichnete Pflicht, den anderen Elternteil beizuziehen, bevor die Kinder über Nacht in die Obhut einer Drittperson gegeben werden) und dies damit begründet hat, dass er nicht dargetan habe, inwiefern der Nichteintretensentscheid des Bezirksrates unzutreffend gewesen sei.
3.1 Am 1. Januar 2013 traten die neuen Bestimmungen zum Erwachsenenschutz, Personenrecht und Kindesrecht in Kraft (AS 2011 725; BBl 2006 7001). Der angefochtene Entscheid erging indes am 28. November 2012 noch unter dem bis zum 31. Dezember 2012 geltenden Recht. In Bezug auf Kindesschutzmassnahmen kam Art. 314 aZGB zur Anwendung, welcher festhielt, dass das Verfahren durch das kantonale Recht geordnet wird. Der Kanton Zürich erklärte dabei die Verfahrensvorschriften der ZPO für subsidiär anwendbar (vgl. angefochtener Entscheid S. 13; mit Hinweis auf §§ 187 ff. des kantonalen Gesetzes über die Gerichts- und Behördenorganisation im Zivil- und Strafprozess vom 10. Mai 2010 [GOG]). Dasselbe gilt im Übrigen auch unter den neuen Bestimmungen des ZGB (vgl. Art. 314 Abs. 1 i.V.m. Art. 450f ZGB).
Im vorliegenden Fall ist die ZPO mithin nicht direkt anwendbar. Vielmehr stellen die Verfahrensvorschriften kantonales Recht dar, dessen Anwendung das Bundesgericht nur auf Willkür (Art. 9 BV) hin prüft. Für die Geltendmachung von Verfassungsverletzungen gilt das strenge Rügeprinzip (Art. 106 Abs. 2 BGG). 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 (<ref-ruling> E. 2.2 S. 246).
3.2 Der Beschwerdeführer erhebt im Zusammenhang mit dem teilweisen Nichteintretensentscheid der Vorinstanz keine Verfassungsrüge, womit das Bundesgericht darauf nicht eintreten kann.
4. 4.1 Die Vorinstanz hat festgestellt, dass die Kommunikation zwischen den Eltern gestört ist und beide dem anderen schlechte Absichten vorwerfen. Die Mutter habe einmal Anzeige erstattet, weil sie vom Vater angegriffen und bedroht worden sei. Der Vater habe zum analogen Mittel gegriffen, weil der Ehemann der Mutter die Kinder einmal geschlagen habe, wobei die Kinder entsprechende Aussagen später zurückgenommen hätten. Dieser Paarkonflikt habe sich gemäss Gutachter Dr. U._ negativ auf die Kinder ausgewirkt. Mit Bezug auf die Betreuungsmöglichkeiten der Parteien hielt die Vorinstanz fest, dass der arbeitstätige Vater die Kinder am Freitag im Gegensatz zur Mutter nicht selber betreuen kann. Der Lebensmittelpunkt der Kinder liege gemäss den Erkenntnissen des Gutachtens bei der Mutter, dort spiele sich der Alltag der Kinder ab. Die vorliegend umstrittene Besuchsrechtsregelung werde zur Zeit eingehalten und gelebt. Wie sich aus dem Gutachten ergebe, habe sich die Besuchssituation seit Einführung der Besuchsregelung beruhigt und die Kinder seien weniger belastet.
4.2 Gestützt auf diese Feststellungen hielt die Vorinstanz ein Besuchswochenende beim Vater alle 14 Tage von Freitag, 18:00 Uhr, bis Sonntag, 18:00 Uhr, für angemessen und ergänzte dieses durch ein Besuchsrecht am Donnerstagabend, 17:00 bis 19:00 Uhr, in der auf das Besuchswochenende folgenden Woche sowie durch ein sechswöchiges Ferienrecht des Vaters. Auf die Festsetzung fixer Telefonzeiten verzichtete die Vorinstanz mit dem Hinweis, dass von den Eltern erwartet werden könne, dass sie dies unter sich regelten; der Gutachter habe darauf hingewiesen, dass die Kinder mit den Telefonaten überfordert seien, weshalb er anstatt der Telefonanrufe das Abendessen am Donnerstag vorgeschlagen habe.
5. Der Beschwerdeführer wirft der Vorinstanz vor, sie habe den Sachverhalt nicht genügend abgeklärt, mithin den Untersuchungsgrundsatz verletzt.
5.1 In Kinderbelangen gelten unabhängig von der Art des Verfahrens die Offizial- und die Untersuchungsmaxime (Art. 296 Abs. 1 ZPO, als kantonales Recht angewendet; vgl. vorstehend E. 3.1). Letztere schreibt dem Gericht vor, den Sachverhalt von Amtes wegen zu erforschen. Die Untersuchungspflicht des Gerichts reicht so weit und dauert so lange, bis über die Tatsachen, die für die Beurteilung des streitigen Anspruchs erforderlich sind, hinreichende Klarheit besteht. Verfügt das Gericht über genügende Grundlagen für eine sachgerechte Entscheidung, kann es auf weitere Beweiserhebungen verzichten (<ref-ruling> E. 2.2.3 S. 735). 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. Ausserdem 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 (Urteil 5A_574/2012 vom 17. Dezember 2012 E. 2.2.1).
5.2 Der Beschwerdeführer begnügt sich damit, immer wieder den Vorwurf zu wiederholen, die Vorinstanz - und überhaupt die bisher befassten Instanzen - hätten die näheren Umstände des Einzelfalles nicht abgeklärt. Er zeigt jedoch nicht auf, welche Abklärungen von der Vorinstanz noch zu treffen gewesen wären und inwiefern diese zu einem anderen Entscheid hätten führen müssen. Namentlich bringt er nicht vor, dass er entsprechende Beweisanträge gestellt hätte, welche die Vorinstanz abgewiesen oder unbeachtet gelassen hätte.
Er unterlässt es ebenso, sich mit dem psychologischen Gutachten vom 28. November 2011 auseinanderzusetzen, welches die Vormundschaftsbehörde B._ in Auftrag gegeben hatte und das der Vorinstanz als Grundlage für ihren Entscheid diente. Die Tochter war zudem am 14. Juli 2011 im Auftrag der Vormundschaftsbehörde B._ durch das Jugendsekretariat des Bezirks Meilen angehört worden. Dass der Sohn damals noch nicht angehört wurde, ist angesichts seines Alters in Übereinstimmung mit der bundesgerichtlichen Praxis (<ref-ruling> E. 1.2.3 S. 557; <ref-ruling> E. 3 S. 554). Schliesslich gab es bereits im Jahr 2010 einen ersten Abklärungsbericht des Jugendsekretariates des Bezirks Meilen (vgl. vorstehend B).
5.3 Daraus ergibt sich, dass die Vorinstanzen sehr wohl den konkreten Fall prüften und durch Fachpersonen untersuchen liessen. Der Vorwurf, es seien keine Abklärungen getätigt worden, geht somit ins Leere. Inwiefern die Untersuchungsmaxime verletzt sein soll, ist weder dargetan noch ersichtlich. Im Übrigen umfasst das ausführliche psychologische Gutachten von Dr. U._ 38 Seiten und wurde nach Anhörung beider Eltern (je drei Gespräche), der beiden Kinder, beider Ehepartner der Parteien, der Psychotherapeutin der Mutter sowie des Beistandes der Kinder erstellt. Die Vorinstanz durfte darauf abstellen (<ref-ruling> E. 2 S. 86). Der Beschwerdeführer hat das Gutachten auch nicht bestritten.
6. Schliesslich rügt der Beschwerdeführer eine Verletzung seines Rechts auf persönlichen Verkehr.
6.1 Eltern, denen die elterliche Sorge oder Obhut nicht zusteht, und das unmündige Kind haben gegenseitig Anspruch auf angemessenen persönlichen Verkehr (Art. 273 Abs. 1 ZGB). Dieses Recht steht dem Betroffenen um seiner Persönlichkeit willen zu (<ref-ruling> E. 3.4 S. 360). Als sog. "Pflichtrecht" dient es freilich in erster Linie dem Interesse des Kindes. Bei der Festsetzung des Besuchsrechts geht es nicht darum, einen gerechten Interessenausgleich zwischen den Eltern zu finden, sondern den elterlichen Kontakt mit dem Kind in dessen Interesse zu regeln, wobei die Bedürfnisse des Kleinkindes nicht denjenigen eines Jugendlichen entsprechen (BGE <ref-ruling> E. 3b/aa S. 232 f.). Als oberste Richtschnur für die Ausgestaltung des Besuchsrechts gilt somit immer das Kindeswohl, das anhand der gegebenen Umstände zu beurteilen ist. Allfällige Interessen der Eltern haben zurückzustehen (<ref-ruling> E. 3b S. 451).
6.2 Der Beschwerdeführer beantragt, ihm sei ein ausgedehnteres Wochenendbesuchsrecht von Donnerstag, 18:00 Uhr, bis Montag, 8:00 Uhr, bzw. bis zum Kindergarten- oder Schulbeginn einzuräumen. Bezüglich Ferien sei festzulegen, dass diese von Samstag, 9:00 Uhr, bis Samstag, 18:00 Uhr, dauern würden. Für die Geburtstage der Kinder verlangt er das Recht, Geschenke vorbeibringen zu dürfen, oder eventualiter einen Telefonanruf zugesprochen zu bekommen. Für den Fall, dass das Wochenendbesuchsrecht nicht ausgedehnt wird, beantragt er eventualiter das Recht, die Kinder wahlweise von Donnerstag auf Freitag oder von Montag auf Dienstag zu sich auf Besuch nehmen zu dürfen; oder es sei ihm ein Telefonrecht an zwei Abenden pro Woche zuzusprechen, vorzugsweise Mittwoch- und Sonntagabend.
Auf den Antrag, die Eltern seien zu verpflichten, erstrangig den anderen Elternteil anzufragen, ob er/sie die Kinder betreuen könne, bevor sie die Kinder über Nacht in die Obhut einer Drittperson oder des Stiefelternteils geben, ist zum Vornherein nicht einzutreten (vgl. vorstehend E. 3).
6.3 Ausgehend von dem in Erwägung 4.1 wiedergegebenen Sachverhalt ist nicht ersichtlich, inwiefern das Obergericht von dem ihm bei der Festlegung der Besuchsrechte zustehenden Ermessen falschen Gebrauch gemacht haben soll. Insbesondere kann der Beschwerdeführer aus <ref-ruling> nichts zu seinen Gunsten ableiten. Diese Rechtsprechung besagt, dass Konfliktsituationen zwischen Elternteilen nicht zu einer übermässigen Einschränkung der Kinderbesuchsrechte führen dürfen. Von einer übermässigen Einschränkung kann vorliegend indes nicht die Rede sein; im Gegenteil kommt dem Beschwerdeführer ein grosszügiges Besuchsrecht zu, das über die verbreitet angewandte Regelung hinausgeht (zusätzliches Besuchsrecht am Donnerstag; Ferienrecht von sechs Wochen). Wenn das Obergericht nicht (noch) ausgedehntere Kontaktrechte gewährt hat, liegt keine falsche Ermessensausübung vor, zumal ein heftiger Elternkonflikt festgestellt wurde und die zur Zeit geltende Regelung gemäss Gutachten zu einer Beruhigung der Situation geführt hat.
Die Bestimmung von Telefonabenden, ausserordentlichen Besuchszeiten an Geburtstagen, Ferienbeginn- und -endzeiten sowie dergleichen gehört zur typischen Ermessensausübung des Sachgerichts, in welche einzugreifen kein Anlass besteht.
Die Beschwerde ist somit abzuweisen, soweit darauf eingetreten wird.
7. Entsprechend dem Ausgang des Verfahrens sind die Gerichtskosten dem Beschwerdeführer aufzuerlegen (Art. 66 Abs. 1 BGG). Der Gegenpartei ist kein entschädigungspflichtiger Aufwand entstanden.

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2. Die Gerichtskosten von Fr. 2'000.-- werden dem Beschwerdeführer auferlegt.
3. Dieses Urteil wird den Parteien und dem Obergericht des Kantons Zürich, II. Zivilkammer, schriftlich mitgeteilt.
Lausanne, 19. März 2013
Im Namen der II. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: von Werdt
Die Gerichtsschreiberin: Friedli-Bruggmann