Sachverhalt:
A. A.a Der 1975 geborene W._ war ab 6. April 2003 für die T._ AG als Bauarbeiter C erwerbstätig, welche ihn ab April 2004 hauptsächlich für Temporäreinsätze bei der J._ AG vermittelte. Da der Betrieb die Bautätigkeit während den Wintermonaten einstellte und ihm auf diesen Zeitpunkt hin gekündigt wurde, meldete sich der Versicherte in den Jahren 2007 bis 2010 jeweils im Dezember beim Regionalen Arbeitsvermittlungszentrum (RAV) Sargans zum Bezug von Leistungen der Arbeitslosenversicherung an.
Mit Verfügung vom 11. Januar 2011 bejahte das RAV die Vermittlungsfähigkeit des Versicherten ab Antragstellung vom 13. Dezember 2010, wies diesen jedoch darauf hin, dass er bei Ausübung einer saisonalen Tätigkeit verpflichtet sei, ohne Unterbruch eine Stelle zu suchen, um das Interesse an einer Dauerstelle zu bekunden. Andernfalls könnten die Beschäftigungslücken künftig nicht mehr als arbeitslosenversicherungsrechtlich relevanter Ausfall an Normalarbeitszeit betrachtet werden, und es müsste bei einer erneuten Antragstellung die Vermittlungsfähigkeit überprüft und voraussichtlich negativ beurteilt werden.
A.b Ab 31. Januar 2011 vermittelte die T._ AG W._ in verschiedenen Betrieben befristete Arbeitsstellen. Am 17. November 2011 meldete sich dieser wiederum zum Bezug von Leistungen der Arbeitslosenversicherung an, nachdem das Arbeitsverhältnis mit der T._ AG am 16. November 2011 erneut aufgelöst worden war. Mit Verfügung vom 28. November 2011 stellte ihn das RAV wegen ungenügender Arbeitsbemühungen für zehn Tage ab 17. November 2011 in der Anspruchsberechtigung ein.
Nach vorgängiger Gewährung des rechtlichen Gehörs sprach das RAV dem Versicherten mit Verfügung vom 5. Dezember 2011 die Vermittlungsfähigkeit ab Antragstellung vom 17. November 2011 ab und verneinte den Anspruch auf Leistungen der Arbeitslosenversicherung. Daran hielt es mit Einspracheentscheid vom 25. Januar 2012 fest.
B. Die dagegen erhobene Beschwerde hiess das Versicherungsgericht des Kantons St.Gallen unter Aufhebung des Einspracheentscheids vom 25. Januar 2012 mit Entscheid vom 22. Oktober 2012 gut und bejahte die Vermittlungsfähigkeit ab Antragstellung.
C. Das Amt für Wirtschaft und Arbeit des Kantons St. Gallen (AWA) führt Beschwerde mit dem Antrag, es sei der Versicherungsgerichtsentscheid vom 22. Oktober 2012 aufzuheben und festzustellen, dass die Vermittlungsfähigkeit ab 17. November 2011 zu verneinen sei.
W._ schliesst auf Abweisung der Beschwerde, während das Staatssekretariat für Wirtschaft (SECO) und das Versicherungsgericht des Kantons St. Gallen auf eine Vernehmlassung verzichten.

Erwägungen:
1. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten (<ref-law>) kann unter anderem die Verletzung von Bundesrecht gerügt werden (<ref-law>). Gemäss <ref-law> legt das Bundesgericht seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat. Es kann deren Sachverhaltsfeststellung von Amtes wegen nur berichtigen oder ergänzen, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht (<ref-law>; vgl. auch <ref-law>). Zu den Rechtsverletzungen gemäss <ref-law> gehören namentlich auch die unvollständige (gerichtliche) Feststellung der rechtserheblichen Tatsachen (<ref-ruling> E. 2 S. 25 mit Hinweisen), die Verletzung des Untersuchungsgrundsatzes als einer wesentlichen Verfahrensvorschrift sowie die Pflicht zu inhaltsbezogener, umfassender, sorgfältiger und objektiver Beweiswürdigung (<ref-law>; <ref-ruling> E. 4.1 S. 400).
2. 2.1 Im angefochtenen Gerichtsentscheid werden die Bestimmungen und Grundsätze über die Vermittlungsfähigkeit als eine der Voraussetzungen für den Anspruch auf Arbeitslosenentschädigung (Art. 8 Abs. 1 lit. f in Verbindung mit <ref-law>), namentlich auch in Bezug auf die Vermittlungsfähigkeit von Personen, die vor ihrer Arbeitslosigkeit temporär beschäftigt waren und daher nur dann als vermittlungsfähig gelten, wenn sie bereit und in der Lage sind, eine Dauerstelle anzunehmen (<ref-law>; <ref-ruling> E. 3b S. 388), zutreffend dargelegt. Darauf wird verwiesen.
2.2 Richtig ist insbesondere, dass nach der Rechtsprechung fortlaufend ungenügende Bemühungen um eine neue Stelle ein wesentlicher Hinweis darauf sein können, dass die versicherte Person während einer bestimmten Zeitspanne überhaupt nicht gewillt war, ihre Arbeitskraft anzubieten, was einen Anspruch auf Arbeitslosenentschädigung ausschliesst. Dies darf aber nicht ohne weiteres aufgrund der blossen Tatsache unzureichender Stellensuche allein gefolgert werden. Auch dürftige Bemühungen um eine neue Arbeit sind in der Regel nur Ausdruck unzureichender Erfüllung der gesetzlichen Schadenminderungspflicht und nicht Folge davon, dass die versicherte Person in der fraglichen Zeit eine neue Anstellung gar nicht finden wollte. Sind immerhin gewisse Anstrengungen festzustellen, kann grundsätzlich nicht auf fehlende Vermittlungsbereitschaft erkannt werden, es sei denn, dass trotz des äusseren Scheins nachweislich keine Absicht zur Wiederaufnahme einer Arbeitnehmertätigkeit bestanden hat. Wurde die Person bereits wegen ungenügender persönlicher Arbeitsbemühungen in der Anspruchsberechtigung eingestellt, lag der entsprechenden Verfügung jedoch nur die Annahme eines leichten Verschuldens zu Grunde, rechtfertigt sich die Verneinung der Anspruchsberechtigung wegen fehlender Vermittlungsfähigkeit nicht. Es widerspricht dem Verhältnismässigkeitsprinzip, wenn einstellungswürdiges Verhalten zunächst mit der leichtesten Massnahme geahndet und dann dieses gleiche Verhalten zum Anlass genommen wird, direkt auf die schwerste Sanktion, die Aberkennung der Vermittlungsfähigkeit, zu schliessen (ARV 1996/1997 Nr. 8 S. 29, C 84/94; bestätigt in den Urteilen C 320/05 vom 20. April 2006 E. 4.1; C 188/05 vom 19. Januar 2006 E. 3).
2.3 Die Frage der Vermittlungsfähigkeit ist prospektiv (<ref-ruling> E. 2 S. 387) und aufgrund einer gesamthaften Würdigung der für die Anstellungschancen im Einzelfall wesentlichen, objektiven und subjektiven Faktoren zu beurteilen. Ausser dem Umfang des für die versicherte Person in Betracht fallenden Arbeitsmarktes ist auch die Art der gesuchten zumutbaren Arbeit von Bedeutung (Urteil 8C_382/2010 vom 1. Juli 2010 E. 2.2).
3. Streitig und zu prüfen ist die Vermittlungsfähigkeit ab 17. November 2011.
3.1 Die Vorinstanz ging davon aus, dass der Beschwerdegegner seit April 2003 über die T._ AG hauptsächlich für die J._ AG tätig gewesen sei. Von April 2004 bis März 2011 habe es sich um einen Temporäreinsatz gehandelt. Während dieser Zeit habe der Versicherte jeweils in den Wintermonaten (Dezember/Januar) Leistungen der Arbeitslosenversicherung beantragt, um danach die Arbeit bei der angestammten Arbeitgeberin für den selben Einsatzbetrieb wieder aufzunehmen. Nachdem die Baustelle offenbar beendet worden sei, habe sich die Beschäftigungssituation im Jahre 2011 anders gestaltet als bisher, indem der Beschwerdegegner (bis zur Vertragsauflösung auf den 16. November 2011) nicht mehr zur Hauptsache bei der J._ AG, sondern über die T._ AG für verschiedene Betriebe zum Einsatz gekommen sei. Dieser habe daher nicht damit rechnen können, im Frühjahr 2012 wieder einen Einsatzvertrag bei der J._ AG zu erhalten.
3.2 Das kantonale Gericht hat weiter erwogen, von Dezember 2009 bis zur Anmeldung bei der Arbeitslosenversicherung vom 17. November 2011 hätten sich die Arbeitsbemühungen des Beschwerdegegners im Wesentlichen auf die arbeitslosen Wintermonate und zur Hauptsache auf Stellen bei der T._ AG, der J._ AG und bei Bergbahnunternehmen beschränkt. Ab dem Zeitpunkt der Einstellungsverfügung vom 28. November 2011 stellte die Vorinstanz bezüglich der Stellenbemühungen des Versicherten eine veränderte Verhaltensweise als in den Vorjahren fest. So habe sich der Beschwerdegegner im Dezember 2011 sowie im Januar und Februar 2012 intensiv um Dauerstellen bemüht, und zwar nicht nur entsprechend seiner Berufsbiographie, sondern unter anderem auch in seinem erlernten Beruf als Forstwart. Daraus schloss das kantonale Gericht, dass die verfügte Einstellung in der Anspruchsberechtigung Wirkung gezeigt und der Beschwerdegegner seinen Willen kundgetan habe, eine Dauerstelle zu finden und aufzunehmen. Der Umstand, dass er seine Bewerbungen nebst anderen auch auf Temporärarbeiten ausgerichtet habe, weise nicht zwingend auf eine ablehnende Haltung gegenüber einer möglichen Festanstellung hin. Demgemäss sei die Vermittlungsfähigkeit ab Antragstellung (17. November 2011) zu bejahen.
3.3 Das AWA wendet gegen die Bejahung der Vermittlungsfähigkeit ab 17. November 2011 ein, der Versicherte sei regelmässig jeweils über die Wintermonate entlassen und anschliessend wiederum für die gleiche Arbeitgeberin tätig gewesen. Der Auflage gemäss Verfügung vom 11. Januar 2011, die drohende Arbeitslosigkeit durch intensive Arbeitsbemühungen während den Temporäreinsätzen zu verhindern, sei er bis zum Zeitpunkt der Antragstellung nur ungenügend nachgekommen. Er sei somit freiwillig bereit gewesen, ausschliesslich Arbeitsverhältnisse einzugehen, welche mit beschäftigungslosen Zeiten verbunden seien, was als Ausdruck fehlender Vermittlungsfähigkeit für Dauerstellen zu werten sei. Damit habe er die saisonal bedingte Arbeitslosigkeit in Kauf genommen mit der Folge, dass die Vermittlungsfähigkeit zwischen den Arbeitseinsätzen zu verneinen sei.
4. 4.1 Dem Beschwerde führenden AWA ist insoweit beizupflichten, als sich die Stellensuche des Beschwerdegegners bis zur Anmeldung bei der Arbeitslosenversicherung am 17. November 2011 im Wesentlichen auf die arbeitslosen Wintermonate beschränkte. Für die Zeit vor der erneuten Arbeitslosigkeit konnte der Versicherte zudem lediglich drei Arbeitsbemühungen nachweisen, wovon eine bei der T._ AG und zwei bei Bergbahnunternehmen. Dieses Verhalten konnte in der Tat Anlass zu Zweifeln an der Bereitschaft des Beschwerdegegners aufkommen lassen, eine Dauerstelle anzunehmen, zumal dauernd qualitativ und teilweise auch quantitativ ungenügende Arbeitssuche schliesslich zur Annahme der Vermittlungsunfähigkeit führen kann (<ref-ruling> E. 3 S. 216). Davon ging auch die Vorinstanz aus. Entgegen der Auffassung des AWA kann die Vermittlungsfähigkeit indessen nicht allein aufgrund der ungenügenden Bemühungen um eine neue Stelle in der Vergangenheit verneint werden (vgl. E. 2.2 hievor). Diese hat das RAV mit Verfügung vom 28. November 2011 überdies unter Annahme eines lediglich leichten Verschuldens sanktioniert (<ref-law>). Aufgrund der prospektiven Beurteilung ist die Vermittlungsfähigkeit vielmehr unter Berücksichtigung der im Zeitpunkt der Gesuchseinreichung (hier: 17. November 2011) vorgelegenen und bis zum Erlass der Ablehnungsverfügung bzw. des Einspracheentscheids (5. Dezember 2011 bzw. 25. Januar 2012) eingetretenen Verhältnisse zu prüfen (E. 2.3 hievor).
4.2 Unter Würdigung der gesamten Aktenlage des massgebenden Prüfungszeitraums stellte die Vorinstanz fest, dass die Einstellung vom 28. November 2011 Wirkung zeigte. Der Beschwerdegegner habe sich nach Erlass der Verfügung vom 5. Dezember 2011 und vor dem Einspracheentscheid vom 25. Januar 2012 - im Gegensatz zu den Vorjahren - intensiv um eine Dauerstelle bemüht. Seine Arbeitsbemühungen umfassten nachweislich auch Tätigkeiten als Pistenmaschinenfahrer, Skiliftangestellter, Ersatzteillagerist, Werkhofmitarbeiter, Operateur, Forstwart und Mitarbeiter der Kanalreinigung. Gemäss Vorinstanz bekunden diese Arbeitsbemühungen den Willen des Beschwerdegegners, eine Dauerstelle zu finden.
4.3 Die Beweiswürdigung im Allgemeinen, einschliesslich der Würdigung von Indizien und fallbezogenen Wahrscheinlichkeiten betreffen Tatfragen, die das Bundesgericht lediglich auf offensichtliche Unrichtigkeit und Rechtsfehlerhaftigkeit hin zu überprüfen befugt ist (<ref-law>; vgl. E. 1 hiervor). Blosse Zweifel an der Richtigkeit der vorinstanzlichen Sachverhaltsfeststellung ändern an deren Verbindlichkeit gemäss <ref-law> nichts (vgl. die Hinweise im bereits erwähnten Urteil 8C_382/2010 E. 3.2.1).
4.4 Die im angefochtenen Gerichtsentscheid getroffenen Überlegungen zur Bereitschaft des Beschwerdegegners, eine Dauerstelle anzunehmen, sind nicht offensichtlich unrichtig, weshalb das Bundesgericht an die Sachverhaltsfeststellung der Vorinstanz gebunden ist. Der Beschwerdeführer bringt denn auch nichts vor, was geeignet wäre, die Sachverhaltsfeststellung des kantonalen Gerichts als unrichtig oder unvollständig erscheinen zu lassen. Die Arbeitsbemühungen nach Erlass der Verfügung vom 5. Dezember 2011 wurden weder im Einspracheentscheid des RAV vom 25. Januar 2012 noch in der Beschwerdeschrift des AWA vom 27. November 2012 als massgeblich betrachtet. Im letztinstanzlichen Verfahren setzt sich das AWA mit der vorinstanzlichen Berücksichtigung der nachträglichen Arbeitsbemühungen im Rahmen der Beurteilung der Vermittlungsfähigkeit nicht auseinander und legt insbesondere nicht dar, inwiefern diese bundesrechtswidrig wäre. Es ist indessen ohne weiteres nachvollziehbar, dass der Beschwerdegegner in der Zeit seit der am 17. November 2011 erfolgten Antragstellung bei der Arbeitslosenkasse feststellte, dass er seinem Willen, eine Dauerstelle zu finden, ernsthaft Nachachtung verschaffen musste, um bei der Stellensuche erfolgreich zu sein. Wenn er anhand der vorgelegten Arbeitsbemühungen zumindest für die vorliegend relevante Zeit deutlich macht, dass er bereit und in der Lage ist, eine Dauerstelle anzunehmen, kann ihm - trotz langjähriger ausschliesslicher Temporärarbeit - der Wille zur Annahme einer solchen Stelle nicht abgesprochen werden.
4.5 Zusammenfassend ist mit der Vorinstanz die Vermittlungsfähigkeit des Versicherten ab der Antragstellung vom 17. November 2011 bei dieser Sachlage zu bejahen.
5. Der Prozess ist grundsätzlich kostenpflichtig (<ref-law>). Das unterliegende AWA handelt in seinem amtlichen Wirkungskreis und nicht in seinem Vermögensinteresse. Es trägt daher keine Verfahrenskosten (<ref-law>; <ref-ruling>), hat jedoch dem obsiegenden Beschwerdeführer eine Parteientschädigung zu bezahlen (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen.
2. Es werden keine Gerichtskosten erhoben.
3. Der Beschwerdeführer hat den Beschwerdegegner für das bundesgerichtliche Verfahren mit Fr. 2800.- zu entschädigen.
4. Dieses Urteil wird den Parteien, dem Versicherungsgericht des Kantons St. Gallen und dem Staatssekretariat für Wirtschaft (SECO) schriftlich mitgeteilt.
Luzern, 16. April 2013
Im Namen der I. sozialrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Leuzinger
Die Gerichtsschreiberin: Hofer