Sachverhalt:
A. A.a X._, türkischer Staatsangehöriger, geboren am 5. Mai 1973, heiratete am 29. Juni 2001 die Schweizer Bürgerin Y._ und erhielt in der Folge eine Aufenthaltsbewilligung im Rahmen des Familiennachzugs, die indessen im Jahre 2006 nicht mehr verlängert wurde. Am 2. März 2007 wurde die Ehe von X._ und Y._ geschieden, worauf X._ am 11. April 2007 die in der Schweiz niedergelassene portugiesische Staatsangehörige Z._, geboren am 19. Dezember 1963, heiratete und in der Folge eine Aufenthaltsbewilligung EG/EFTA erhielt.
A.b Am 29. November 2010 stellten X._ und Z._ das Gesuch um Familiennachzug der in der Türkei lebenden Kinder von X._, A._ (geboren am 10. Dezember 1993), B._ (geboren am 23. Januar 1996) und C._ (geboren am 4. Mai 1997). Das Migrationsamt des Kantons St. Gallen wies das Gesuch am 23. September 2011 ab.
B. X._, A._, B._ und C._ erhoben dagegen erfolglos Rekurs an das Sicherheits- und Justizdepartement (Entscheid vom 20. März 2012) und an das Verwaltungsgericht des Kantons St. Gallen (Urteil vom 15. Oktober 2012).
C. X._, A._, B._ und C._ erheben mit Eingabe vom 19. November 2012 Beschwerde in öffentlich-rechtlichen Angelegenheiten an das Bundesgericht. Sie beantragen, das Urteil des Verwaltungsgerichts sei aufzuheben und es sei das Migrationsamt anzuweisen, den Kindern A._, B._ und C._ eine Aufenthaltsbewilligung zum Verbleib beim Vater und dessen Ehefrau zu erteilen.
Das Sicherheits- und Justizdepartement und das Verwaltungsgericht St. Gallen sowie das Bundesamt für Migration beantragen Abweisung der Beschwerde.

Erwägungen:
1. 1.1 Die Beschwerdeführer berufen sich in vertretbarer Weise auf einen Bewilligungsanspruch gemäss dem Abkommen vom 21. Juni 1999 zwischen der Schweizerischen Eidgenossenschaft einerseits und der Europäischen Gemeinschaft und ihren Mitgliedstaaten andererseits über die Freizügigkeit (FZA; SR 0.142.112.681), so dass die Beschwerde in öffentlich-rechtlichen Angelegenheiten gegen den kantonal letztinstanzlichen Endentscheid zulässig ist (Art. 82 lit. a, Art. 83 lit. c Ziff. 2, Art. 86 Abs. 1 lit. d sowie Art. 90 BGG); ob der Anspruch effektiv besteht, ist Sache der materiellen Beurteilung (<ref-ruling> E. 1.1 S. 179).
1.2 Das Bundesgericht prüft frei die Anwendung von Bundesrecht mit Einschluss des Verfassungs- und Völkerrechts (Art. 95 lit. a und b BGG). Es legt seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat; es kann die Sachverhaltsfeststellung der Vorinstanz berichtigen oder ergänzen, wenn sie offensichtlich unrichtig, d.h. willkürlich ist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht und wenn die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein kann (Art. 97 Abs. 1 und Art. 105 Abs. 1 und 2 BGG). Entsprechende Mängel müssen in der Beschwerde entsprechend gerügt werden; rein appellatorische Kritik am angefochtenen Entscheid ist nicht zu hören (<ref-law>; <ref-ruling> E. 2.2 S. 246).
1.3 Neue Tatsachen und Beweismittel dürfen vor Bundesgericht nur so weit vorgebracht werden, als erst der Entscheid der Vorinstanz dazu Anlass gibt (<ref-law>). Die Beschwerdeführer reichen einige Noven ein und begründen dies damit, diese seien dadurch veranlasst, dass die Vorinstanz das rechtliche Gehör verletzt habe. Ob dies die Noven rechtfertigt, kann mit Blick auf das Folgende offen bleiben.
2. 2.1 Vorinstanz und Beschwerdeführer gehen übereinstimmend von der mit <ref-ruling> begründeten bundesgerichtlichen Rechtsprechung aus, wonach auch Stiefkinder mit Drittstaatsangehörigkeit eines EU-Angehörigen in den Anwendungsbereich von Art. 3 Anhang I FZA fallen. Vorausgesetzt ist, dass der EU-Angehörige, um dessen Personenfreizügigkeit es letztlich geht, mit dem Nachzug der Stiefkinder einverstanden ist, da dieser sonst gar nicht der Gewährleistung des Freizügigkeitsrechts dient. Weiter sind familienrechtliche Scheinbeziehungen vom Nachzugsrecht auszuschliessen. In diesem Sinne ist zu verlangen, dass bereits vor der Familienvereinigung ein (soziales) Familienleben tatsächlich bestanden hat, wobei die Angehörigen freilich nicht zusammengewohnt, wohl aber ihre Beziehung mit minimaler Intensität gelebt haben müssen. Bei Minderjährigen hat der nachziehende Ehegatte sodann die zivilrechtliche Verantwortung für das Kind zu tragen, d.h. er muss entweder über das Sorgerecht oder bei geteiltem Sorgerecht über das Einverständnis des anderen Elternteils verfügen. Damit die nachzuziehenden Angehörigen bei der freizügigkeitsberechtigten Person Wohnung nehmen können, hat dafür auch eine Wohnung vorhanden zu sein, die den für Inländer geltenden normalen Anforderungen entspricht (Art. 3 Abs. 1 Anhang I FZA). Zu beachten ist überdies der Vorbehalt der öffentlichen Ordnung, Sicherheit und Gesundheit gemäss Art. 5 Anhang I FZA. Schliesslich darf der Nachzugsentscheid der Eltern nicht in offensichtlichem Widerspruch zum Kindeswohl stehen (<ref-ruling> E. 5.2 S. 76 f.; <ref-ruling> E. 3.2.3 S. 186).
2.2 Die Vorinstanz hat erwogen, der Beschwerdeführer 1 habe seine Kinder erst im Jahr 2010 formell anerkannt und sich das Sorgerecht übertragen lassen, als diese bereits 17, 14 bzw. 13 Jahre alt gewesen seien. Aus den Akten hätten sich bis zur Stellung des Familiennachzugsbegehrens keine Anhaltspunkte ergeben, wonach der Beschwerdeführer 1 Kinder haben könnte. Es gebe auch keine Hinweise darauf, dass er sich vorher darum bemüht habe, die Vaterschaft anzuerkennen und sich die elterliche Sorge übertragen zu lassen, um die Kinder in die Schweiz nachziehen zu können. Auch bei früheren Befragungen habe der Beschwerdeführer 1 nie Kinder erwähnt. Der Beschwerdeführer habe auch seine Behauptung, er habe die Kinder in der Türkei regelmässig besucht und komme seit seiner Einreise in die Schweiz für deren Unterhalt auf, nicht näher begründet; aus den Akten ergäben sich dafür keine Hinweise. Aktenkundig sei hingegen, dass er die Kinder erst im Jahre 2010 im Hinblick auf das Familiennachzugsgesuch anerkannt und sich das Sorgerecht habe übertragen lassen. Die gesamten Umstände liessen nicht darauf schliessen, dass zwischen dem Beschwerdeführer 1 und den Beschwerdeführern 2-4 eine tatsächlich gelebte familiäre Beziehung bestehe und das Gesuch gestellt worden sei, um in der Schweiz ein intensives Familienleben führen zu können; das erscheine auch deshalb nicht glaubhaft, weil sich die Betreuungssituation offenbar schon 2006 geändert habe und seit August 2007 die Möglichkeit bestanden hätte, gestützt auf das FZA ein Familiennachzugsgesuch zu stellen; es sei eher davon auszugehen, dass der Nachzug der Beschwerdeführer 2-4 dazu dienen soll, ihnen in der Schweiz zu besseren Berufs- und Lebenschancen zu verhelfen. Zudem sei offen, ob die Ehefrau des Beschwerdeführers 1 mit dem Nachzug nach wie vor einverstanden sei; bei den Akten liege nur eine im Rahmen des Gesuchsverfahrens eingereichte undatierte Erklärung der Ehefrau, aber diese habe am Rekurs- und Beschwerdeverfahren nicht teilgenommen. Insgesamt sei aufgrund der Umstände anzunehmen, das Verfahren sei in rechtsmissbräuchlicher Weise eingeleitet worden.
3. 3.1 Die Beschwerdeführer bestätigen, dass die Kinder nach der Ausreise des Beschwerdeführers 1 in die Schweiz zunächst bei ihrer Mutter, dann beim Bruder des Beschwerdeführers 1 und ab 2006 bei dessen Mutter (also ihrer Grossmutter) lebten und erst im Jahre 2010 das Sorgerecht auf den Vater übertragen wurde und dieser ein Familiennachzugsbegehren stellte. Sie stellen auch nicht in Frage, dass der Beschwerdeführer 1 gegenüber den schweizerischen Behörden vorher seine Kinder nie erwähnt hatte.
3.2 Die Beschwerdeführer rügen hingegen eine Verletzung des Anspruchs auf rechtliches Gehör und eine offensichtlich unrichtige Sachverhaltsfeststellung: Migrationsamt und Departement hätten keine Zweifel am Bestand einer tatsächlich gelebten Beziehung geäussert, weshalb für sie kein Anlass bestanden habe, diese vor Verwaltungsgericht näher zu belegen. Zudem hätten sie für den Fall, dass solche Zweifel bestünden, eine Anhörung der Kinder beantragt, worauf die Vorinstanz nicht eingegangen sei. Hätte die Vorinstanz trotzdem noch Zweifel am Bestand einer gelebten familiären Beziehung gehabt, hätte sie weitere Belege einfordern müssen. Sodann sei die Feststellung der Vorinstanz offensichtlich unrichtig, wonach sich aus den Akten keine Anhaltspunkte auf regelmässige familiäre Besuche in der Türkei und Zahlungsüberweisungen an die Kinder fänden; dies habe der Beschwerdeführer 1 vielmehr mit Schreiben vom 4. Mai 2011 an das Migrationsamt belegt.
3.3 Dass die unteren Instanzen keine Zweifel am Bestehen einer tatsächlichen Familienbeziehung geäussert hätten, trifft nicht zu: Sie haben sich auf Rechtsmissbrauch bezogen, was weitgehend mit der Frage zusammenfällt, ob die familiäre Beziehung bisher bereits gelebt worden ist (<ref-ruling> E. 2.3.1 S. 290; <ref-ruling> E. 4.3 S. 507). Zudem hat bereits das Migrationsamt in seinem Schreiben vom 15. April 2011, womit das rechtliche Gehör zur beabsichtigen Verweigerung der Bewilligung gewährt wurde, ausgeführt, der Beschwerdeführer 1 habe die Kinder erst im Februar 2010 anerkannt, und gemäss Sorgerechtsurteil seien die Kinder einzig aus wirtschaftlichen Gründen dem Vater zugesprochen worden; es stehe daher eindeutig nicht die Familienzusammenführung im Vordergrund. Die Beschwerdeführer äusserten sich denn auch in ihrem Schreiben vom 4. Mai 2011 zum Vorwurf, es stehe nicht die Familienzusammenführung im Vordergrund. Das Sicherheits- und Justizdepartement hat im Rekursentscheid vom 20. März 2012 erwogen, der Beschwerdeführer 1 habe seit Jahren darauf verzichtet, mit den Kindern in einer Familiengemeinschaft zu leben und bringe keine triftigen Gründe vor, warum er erst ein Familiennachzugsgesuch gestellt habe, als die Kinder 17, 14 und 12 1⁄2 Jahre alt gewesen seien; es erscheine bei dieser Sachlage und nach jahrelanger Trennung nicht glaubhaft, dass ein familiäres Zusammenleben ein echtes Anliegen sein soll; die geltend gemachten regelmässigen Kontakte und die finanzielle Unterstützung vermöchten das alltägliche Zusammenleben als Familie nicht zu ersetzen. Schon die Verwaltungsinstanzen haben somit wesentlich darauf abgestellt, dass es ihres Erachtens in Wirklichkeit gar nicht um die Fortführung eines tatsächlich gelebten Familienlebens gehe. Die Beschwerdeführer haben denn auch in ihrer Beschwerde an das Verwaltungsgericht geltend gemacht, es bestehe eine intakte Beziehung zu den Kindern; diese sei aufgrund der regelmässigen Kontakte zu seinen Kinder ohne Weiteres gegeben.
3.4 Zutreffend ist hingegen die Kritik der Beschwerdeführer an der vorinstanzlichen Aussage, es ergäben sich aus den Akten keine Anhaltspunkte, die auf regelmässige familiäre Besuche in der Türkei und auf Zahlungsüberweisungen schliessen lassen könnten. Mit Brief vom 4. Mai 2011 an das Migrationsamt haben die Beschwerdeführer Kopien von Bankauszügen und dem Pass des Beschwerdeführers 1 eingereicht; danach hat dieser in den Jahren 2002 bis 2011 insgesamt rund Fr. 25'000.-- an D._ bzw. E._ in der Türkei (offenbar dessen Bruder bzw. Mutter) überwiesen und ist er einige Male in die Türkei gereist. Es ergeben sich damit entgegen der Auffassung der Vorinstanz durchaus gewisse Anhaltspunkte für Zahlungsüberweisungen und familiäre Besuche.
4. 4.1 In Bezug auf die rechtliche Würdigung bringen die Beschwerdeführer vor, Art. 3 Abs. 1 Anhang I FZA sehe im Unterschied zu Art. 47 AuG keine Fristen für den Familiennachzug vor und setze auch keine triftigen Gründe für einen solchen voraus. Es sei nicht rechtsmissbräuchlich, ein Nachzugsgesuch erst kurz vor dem Ablauf des 21. Lebensjahrs der Kinder zu stellen. Die Weisungen des Bundesamts für Migration, die in einem solchen Fall von der Vermutung eines rechtsmissbräuchlichen Vorgehens ausgingen, stünden im Widerspruch zum FZA.
4.2 Diese Kritik geht insofern ins Leere, als die Vorinstanz nicht davon ausgegangen ist, es liege grundsätzlich Rechtsmissbrauch vor, wenn ein Familiennachzugsgesuch erst nachträglich gestellt wird. Sie ist vielmehr im konkreten Fall unter Würdigung der Umstände zum Ergebnis gekommen, die Berufung auf das FZA sei rechtsmissbräuchlich. Auch nach der Rechtsprechung des EuGH ist die missbräuchliche Berufung auf die Normen des Unionsrechts nicht gestattet und die nationalen Gerichte sind befugt, in jedem Einzelfall dem missbräuchlichen Verhalten der Betroffenen auf der Grundlage objektiver Kriterien Rechnung zu tragen, um die Berufung auf das einschlägige Unionsrecht zu verwehren, wobei die Ziele der fraglichen unionsrechtlichen Bestimmungen zu beachten sind (Urteil des EuGH vom 21. Juli 2011 C-186/10 Oguz Randnr. 25 mit Hinweisen). Dasselbe gilt im Rahmen des FZA und insbesondere für die Bestimmungen über den Familiennachzug: Diese haben zum Ziel, das tatsächlich gelebte Familienleben der Bürger der Staatsvertragsparteien zu ermöglichen; geht es in Wirklichkeit nicht um diesen Zweck, ist eine Beschränkung des Nachzugs nicht geeignet, die im FZA verankerte Personenfreizügigkeit massgeblich zu beeinträchtigen (<ref-ruling> E. 3.2.3 S. 186). Im Urteil 2C_195/2011 vom 17. Oktober 2011 E. 4.3 hat das Bundesgericht den Familiennachzug eines Stiefkindes verweigert, das im Zeitpunkt des Gesuchs 19jährig war und bisher bei seiner Grossmutter in Kongo gelebt hatte, weil nicht glaubhaft gemacht worden war, dass eine Beziehung mit der in der Schweiz lebenden Mutter aufrechterhalten worden war; dass die Mutter finanzielle Beiträge an den Unterhalt des Kindes überwiesen hatte, genügte nicht. Auch gemäss <ref-ruling> E. 2.8 S. 295 (im Rahmen eines Familiennachzugsgesuchs, das innert der Fristen von Art. 47 AuG gestellt wurde) genügt es nicht, wenn der in der Schweiz lebende Elternteil zum Unterhalt der im Ausland lebenden Kinder finanziell beigetragen und regelmässige telefonische Kontakte hatte.
4.3 Im konkreten Fall sprechen zwar einige der von der Vorinstanz genannten Gründe dafür, dass es in Wirklichkeit nicht um die Weiterführung bzw. Ermöglichung einer gelebten Familienbeziehung geht; sie schliessen eine solche aber auch nicht aus. Die beim Migrationsamt eingereichten Unterlagen (vgl. E. 3.4 hiervor) liefern zwar gewisse Anhaltspunkte, vermögen für sich alleine eine hinreichende Beziehung aber nicht zu belegen. Es ist auch nicht klar, ob die überwiesenen Gelder (ausschliesslich oder primär) für den Unterhalt der Kinder bestimmt waren, zumal die Zahlungen unregelmässig erfolgten; näher zu prüfen wäre, ob die nicht unerheblichen Geldzahlungen ausreichten, um - für türkische Verhältnisse - ein tatsächliches soziales Familienleben zu begründen (vgl. E. 4.2 hiervor). Sodann belegen die Stempel im Pass zwar Reisen des Beschwerdeführers 1 in die Türkei, weshalb es prima vista plausibel scheint, dass er dort eine gewisse Zeit mit seinen Kindern verbracht hat; damit ist aber der Nachweis eines in der Türkei gelebten sozialen Familienlebens noch nicht erbracht.
Immerhin sind aber diese Unterlagen, die von der Vorinstanz zu Unrecht gar nicht gewürdigt wurden, Anhaltspunkte für das Bestehen eines tatsächlichen Familienlebens. Zudem hatten die Beschwerdeführer vor der Vorinstanz weitere Beweisanträge gestellt, um das Familienleben nachzuweisen. Wenn die Vorinstanz angesichts dieser von den Beschwerdeführern eingereichten Unterlagen und geltend gemachten Umstände Zweifel an der gelebten familiären Beziehung hatte, so hätte sie die von den Beschwerdeführern beantragten oder (im Rahmen des Untersuchungsgrundsatzes) andere zweckdienliche Beweismassnahmen (insbesondere eine Befragung des Beschwerdeführers 1 und dessen Ehefrau) durchführen müssen. Es kann nicht Sache des Bundesgerichts sein, dies nachzuholen, zumal auch die vor Bundesgericht eingereichten Noven zwar neue Anhaltspunkte liefern, aber ein vorbestandenes Familienleben auch nicht hinreichend zu belegen vermögen. Die Sache ist daher zur Vervollständigung des Sachverhalts und zur beförderlichen Neubeurteilung im Sinne der Erwägungen an die Vorinstanz zurückzuweisen.
5. Die Rückweisung zu erneutem Entscheid mit offenem Ausgang gilt praxisgemäss als Obsiegen der beschwerdeführenden Partei (<ref-ruling> E. 7 S. 271; Urteil 2C_60/2011 vom 12. Mai 2011 E. 2.4). Es sind daher keine Gerichtskosten zu erheben (<ref-law>). Der Kanton St. Gallen hat den Beschwerdeführern für das bundesgerichtliche Verfahren eine Parteientschädigung zu bezahlen (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird gutheissen. Das Urteil des Verwaltungsgerichts des Kantons St. Gallen vom 15. Oktober 2012 wird aufgehoben. Die Sache wird zu neuer Entscheidung im Sinne der Erwägungen an die Vorinstanz zurückgewiesen.
2. Es werden keine Kosten erhoben.
3. Der Kanton St. Gallen hat den Beschwerdeführern für das bundesgerichtliche Verfahren eine Parteientschädigung von Fr. 2'000.-- zu bezahlen.
4. Dieses Urteil wird den Beschwerdeführern, dem Migrationsamt des Kantons St. Gallen, dem Sicherheits- und Justizdepartement des Kantons St. Gallen, dem Verwaltungsgericht des Kantons St. Gallen und dem Bundesamt für Migration schriftlich mitgeteilt.
Lausanne, 13. Mai 2013
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Zünd
Der Gerichtsschreiber: Winiger