Sachverhalt:
A. Der 1955 geborene S._, Forstingenieur ETH, war seit 1. November 1991 beim Amt X._ angestellt. Diese Stelle wurde ihm am 21. Januar 2008 per 30. April 2008 gekündigt. Am 30. April 2008/23. August 2007 meldete er sich zum Bezug von Arbeitslosenentschädigung an. Das Amt für Industrie, Gewerbe und Arbeit (KIGA) stellte ihn mit Verfügung vom 9. Juni 2008 wegen ungenügender Arbeitsbemühungen vor Beginn der Arbeitslosigkeit für vier Tage ab 30. April 2008 in der Anspruchsberechtigung ein. Dabei sei berücksichtigt worden, dass der Versicherte in der Zeit vor Beginn der Arbeitslosigkeit resp. bis 6. März 2008 zu 100 % und vom 7. März bis 14. März 2008 (recte wohl 30. April 2008) zu 80 % arbeitsunfähig gewesen sei. Auf Einsprache hin hielt es daran fest (Einspracheentscheid vom 8. Januar 2009).
B. Das Verwaltungsgericht des Kantons Graubünden wies die dagegen erhobene Beschwerde mit einzelrichterlichem Entscheid vom 6. Mai 2009 ab.
C. Der Versicherte lässt Beschwerde in öffentlich-rechtlichen Angelegenheiten führen mit den Rechtsbegehren, unter Aufhebung des Einsprache- und des kantonalen Gerichtsentscheides sei auf die Einstellung in der Anspruchsberechtigung zu verzichten; eventuell sei die Sache zum entsprechenden Entscheid an eine der Vorinstanzen zurückzuweisen.
Das KIGA und das Staatssekretariat für Wirtschaft verzichten auf eine Vernehmlassung.

Erwägungen:
1. 1.1 Die Beschwerde in öffentlich-rechtlichen Angelegenheiten (<ref-law>) kann wegen Rechtsverletzung gemäss Art. 95 f. BGG erhoben werden. Das Bundesgericht wendet das Recht von Amtes wegen an (<ref-law>). Es ist somit weder an die in der Beschwerde geltend gemachten Argumente noch an die Erwägungen der Vorinstanz gebunden; es kann eine Beschwerde aus einem anderen als dem angerufenen Grund gutheissen und es kann sie mit einer von der Argumentation der Vorinstanz abweichenden Begründung abweisen (vgl. <ref-ruling> E. 2.5 S. 262; <ref-ruling> E. 1.4 S. 140). Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat (<ref-law>). Es kann die Sachverhaltsfeststellung der Vorinstanz von Amtes wegen berichtigen oder ergänzen, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht (<ref-law>) und wenn die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein kann (<ref-law>).
1.2 Der Untersuchungsgrundsatz zählt zu den in <ref-law> erwähnten bundesrechtlichen Vorschriften. Die unvollständige (gerichtliche) Feststellung der rechtserheblichen Tatsachen (<ref-ruling> E. 2 S. 25 mit Hinweisen; Ulrich Meyer, in: Basler Kommentar, Bundesgerichtsgesetz, 2008, N. 25, 36 und 58-61 zu <ref-law>; Hansjörg Seiler, in: Bundesgerichtsgesetz [BGG], 2007, N. 24 zu <ref-law>), die Verletzung des Untersuchungsgrundsatzes als einer wesentlichen Verfahrensvorschrift (statt vieler: Urteil 9C_850/2008 vom 6. Februar 2009 E. 2.2 mit Hinweis; Ulrich Meyer, a.a.O., N. 60 zu <ref-law>; Markus Schott, in: Basler Kommentar, Bundesgerichtsgesetz, 2008, N. 17 ff. zu <ref-law>) sowie der Pflicht zu inhaltsbezogener, umfassender, sorgfältiger und objektiver Beweiswürdigung (<ref-law>; <ref-ruling> E. 4.1 S. 400) stellen eine Rechtsverletzung gemäss <ref-law> dar. Hat das kantonale Gericht die rechtserheblichen tatsächlichen Feststellungen in Verletzung des Untersuchungsgrundsatzes getroffen, sind sie für das Bundesgericht nicht verbindlich (Urteil 8C_773/2008 vom 11. Februar 2009 E. 5.4, in: SVR 2009 EL Nr. 5 S. 17).
2. Streitig und zu prüfen ist, ob der Beschwerdeführer zu Recht wegen ungenügenden Arbeitsbemühungen für die Dauer von vier Tagen in der Anspruchsberechtigung eingestellt worden ist.
3. 3.1 Das kantonale Gericht hat die massgebenden Bestimmungen über die Pflicht der versicherten Person, alles Zumutbare zu unternehmen, um Arbeitslosigkeit zu vermeiden oder zu verkürzen und ihre entsprechenden Bemühungen nachzuweisen (<ref-law>, <ref-law>), die Einstellung in der Anspruchsberechtigung bei ungenügenden persönlichen Arbeitsbemühungen (<ref-law>) sowie die verschuldensabhängige Dauer der Einstellung (<ref-law> in Verbindung mit <ref-law>) zutreffend dargelegt. Darauf wird verwiesen. Gleiches gilt für die Feststellung im Einspracheentscheid, wonach die versicherte Person verpflichtet ist, sich bereits während der Kündigungsfrist um einen neuen Arbeitsplatz zu bewerben (vgl. auch Urteil 8C_21/2008 vom 3. Juni 2008 mit Hinweisen; ARV 2005 Nr. 4 S. 56 E. 3.1 S. 58 [C 208/03), 2003 Nr. 10 S. 119 E. 1 [C 305/01] und 1993/94 Nr. 26 S. 184 E. 2b).
4. 4.1 Das kantonale Gericht hat im angefochtenen Entscheid erwogen, in tatsächlicher Hinsicht sei erstellt, dass der Beschwerdeführer in den Monaten März und April 2008 bzw. im Zeitraum vom 7. März 2008 bis 30. April 2008 lediglich drei Arbeitsbemühungen (eine im März sowie zwei im April) getätigt habe. Es ging davon aus, dass bei einer Arbeitsunfähigkeit von 80 % drei monatliche Arbeitsbemühungen zumutbar seien. Die geringe Restarbeitsfähigkeit des Versicherten vermöge wohl das Finden einer neuen Arbeitsstelle, nicht aber das Bemühen um Abwendung der Arbeitslosigkeit erschwert haben, was vorliegend allein von Bedeutung sei. Im Rahmen der Schadenminderungspflicht sei dieser verpflichtet, auch ausserhalb seines angestammten Berufes eine Stelle zu suchen. Er habe sich bei seinen Bemühungen lediglich auf Stellenangebote in seiner Branche als Forstwart bzw. dieser Branche berufsnahe Stellen beschränkt, womit er seiner Schadenminderungspflicht nur in ungenügender Weise nachgekommen sei. Er wäre verpflichtet gewesen, seine Arbeitsbemühungen auch auf andere bzw. branchenfremde Arbeitsstellen auszuweiten, deren Ausübung ihm aufgrund seiner Fähigkeiten oder seiner Ausbildung möglich und zumutbar gewesen wäre. Insgesamt beurteilte das kantonale Gericht die Arbeitsbemühungen des Versicherten nicht nur in quantitativer Hinsicht, sondern auch hinsichtlich deren Intensität als ungenügend und bestätigte die Einstellung in der Anspruchsberechtigung als rechtmässig.
4.2 Der Beschwerdeführer wendet dagegen ein, die Vorinstanz habe den Sachverhalt unzutreffend bzw. unvollständig festgestellt, indem sie davon ausging, dass der Anspruch auf Arbeitslosenentschädigung am 30. April 2008 angemeldet worden sei. Mit Verweis auf das Formular "Antrag auf Arbeitslosenentschädigung" macht er geltend, dieses datiere vom 23. August 2007. Er habe somit die bevorstehende Arbeitslosigkeit schon sehr früh angemeldet, weshalb er habe davon ausgehen dürfen, dass insbesondere mit Rücksicht auf seine Krankheit, die bis 14. März 2008 100 % betragen habe, er auf seine Pflichten als Arbeitsloser hätte aufmerksam gemacht werden müssen.
Zwar spricht mit dem Beschwerdeführer vieles dafür, insbesondere der Stempel auf dem Formular mit Datum vom 27. September 2007, dass die Anmeldung bereits am 23. August 2007 erfolgte und der Sachverhalt diesbezüglich unzutreffend festgestellt worden ist. Allerdings ist die Behebung des Mangels für den Ausgang des Verfahrens nicht relevant. Der Versicherte kann sich nicht damit exkulpieren, nicht gewusst zu haben, dass er schon vor Aufnahme der Stempelkontrolle zur ernsthaften Arbeitssuche verpflichtet war und nicht darauf aufmerksam gemacht worden sei (Urteile M. vom 28. Dezember 2004 [C 236/04] P. vom 15. Dezember 2003 [C 200/03] je mit Hinweis; vgl. auch ARV 1980 Nr. 44 S. 109). Die Pflicht der Versicherungsleistungen beanspruchenden Person zur Arbeitssuche - als Teil der Schadenminderungspflicht - ergibt sich direkt aus dem Gesetz (<ref-law>). Der Versicherte hat sich dementsprechend während einer allfälligen Kündigungsfrist, aber auch generell während der Zeit vor Anmeldung (ARV 1982 Nr. 4 S. 40) unaufgefordert um Stellen zu bemühen (ARV 2006 S. 295 E. 2.1, C 138/05).
4.3 In der Sache selbst macht der Beschwerdeführer geltend, die Vorinstanz habe ihren Ermessensspielraum überdehnt und sei damit in Willkür verfallen, wenn sie die zumutbaren Arbeitsbemühungen auf mindestens drei monatlich festlege. Gehe man davon aus, dass bei voller Arbeitsfähigkeit mindestens sieben Arbeitsbemühungen pro Monat verlangt werden dürften, wie es die Vorinstanz offenbar annehme, ergäben sich bei den für den fraglichen Zeitraum massgeblichen 20 % Arbeitsfähigkeit und linearer Interpolation lediglich 1,4 Arbeitsbemühungen pro Monat. Im März 2008 (rund ein halber Monat nicht vollständige Arbeitsunfähigkeit) habe es aber eine Arbeitsbemühung, also mehr als die dann massgeblichen 0,7 und im April gar drei, also mehr als das Doppelte des Zumutbaren gegeben.
5. 5.1 Bei der Beurteilung der Frage, ob sich eine Person genügend um zumutbare Arbeit bemüht hat, ist nicht nur die Quantität, sondern auch die Qualität ihrer Bewerbungen von Bedeutung (<ref-ruling> E. 4a S. 231 mit Hinweis). Was die Quantität der persönlichen Arbeitsbemühungen anbelangt, können keine eindeutigen Zahlenwerte angegeben werden. Eine allgemein gültige Aussage über die erforderliche Mindestzahl an Bewerbungen ist nicht möglich. Das Quantitativ beurteilt sich vielmehr nach den konkreten Umständen (<ref-ruling> E. 4a S. 231 mit Hinweis). Die Verwaltungspraxis verlangt in der Regel 10 bis 12 Bewerbungen pro Monat, wobei es sich nicht um eine starre Grenze handelt, sondern die subjektiven und objektiven Umstände des Einzelfalls zu berücksichtigen sind (vgl. Urteil C 62/06 vom 7. August 2006 mit Hinweisen; Gerhard Gerhards, Kommentar zum Arbeitslosenversicherungsgesetz, [AVIG] Bd. I, [Art. 1-58], 1988, N 15 zu <ref-law>). Dabei sind die persönlichen Umstände und Möglichkeiten der versicherten Person wie Alter, Schul- und Berufsbildung sowie die Usanzen des für sie in Betracht fallenden Arbeitsmarktes zu beachten (<ref-ruling> E. 4a S. 78 vgl. Gerhard Gerhards, N 15 zu <ref-law>; Thomas Nussbaumer, Arbeitslosenversicherung, in: Soziale Sicherheit, SBVR Bd. XIV, 2. Aufl. 2007, S. 2430 Rz. 839). Zudem ist auch zu berücksichtigen wie lange eine Arbeitslosigkeit bereits dauert und wie die Chancen der betreffenden Person auf dem Arbeitsmarkt stehen. Insgesamt gilt es bei der Würdigung des Verhaltens des Versicherten unter dem Gesichtspunkt des Verschuldens alle Umstände des konkreten Einzelfalls einzubeziehen.
5.2 In tatsächlicher Hinsicht hat die Vorinstanz für das Bundesgericht grundsätzlich verbindlich festgestellt, dass der Beschwerdeführer vor Eintritt der Arbeitslosigkeit bzw. während der dreimonatigen Kündigungsfrist zwei Arbeitsbemühungen im Januar, je eine in den Monaten Februar und März sowie zwei im April 2008 getätigt hat. Wenn der Beschwerdeführer nunmehr von drei Bewerbungen im Monat April spricht, kann dies als neues Vorbingen im Sinne von Art. 99 <ref-law> letztinstanzlich nicht gehört werden. Unbestritten ist, dass es sich um schriftliche, sorgfältig ausgearbeitete Bewerbungen für qualifizierte Stellen in seiner Branche oder in berufsnahen Bereichen handelt. Fest steht zudem, dass der Beschwerdeführer vor und während der dreimonatigen Kündigungsfrist von Februar bis 7. März 2008 zunächst 100 % und anschliessend noch 80 % arbeitsunfähig war (Arztzeugnis des Dr. med. G._, Kinder- und Jugendpsychiater FMH, vom 26. Juni 2008), und mithin während der hier relevanten Zeit vor Eintritt der Arbeitslosigkeit gesundheitlich erheblich eingeschränkt war. Weiter ist der Tatsache Rechnung zu tragen, dass der Beschwerdeführer während 17 Jahren an der gleichen Arbeitsstelle als Forstingenieur tätig war, es sich also um eine langjährige qualifizierte Arbeit handelte. Er hatte sich also in der Zeit vor der Arbeitslosigkeit trotz gesundheitlicher Beeinträchtigung insgesamt sechsmal und zwar unbestrittenermassen mit qualifizierten Bewerbungen um eine Stelle bemüht. Dass er während der Kündigungsfrist ausschliesslich in seinem Berufsfeld Arbeit gesucht hat, kann ihm mit Blick auf die gesamte Situation nicht angelastet werden. Die Schadenminderungspflicht gilt unter Beachtung der Zumutbarkeitsregeln von <ref-law> (Gerhard Gerhards, a.a.O., N 13 zu <ref-law>).
5.3 Zusammenfassend ist festzustellen, dass bei dieser Ausgangslage im Rahmen der für die Verschuldensbeurteilung erforderlichen Gesamtwürdigung nicht gesagt werden kann, der Beschwerdeführer habe sich nicht genügend um zumutbare Arbeit bemüht. Die Einstellung in der Anspruchsberechtigung aufgrund von <ref-law> erfolgte mithin zu Unrecht. Die Beschwerde ist daher gutzuheissen.
6. Das Verfahren ist grundsätzlich kostenpflichtig. Das unterliegende KIGA ist jedoch gestützt auf <ref-law> von den Gerichtskosten befreit (<ref-ruling>). Es hat dem anwaltlich vertretenen Beschwerdeführer eine Parteientschädigung zu bezahlen (Art. 68 Abs. 1 und 2 BGG).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird gutgeheissen. Der Entscheid des Verwaltungsgerichts des Kantons Graubünden vom 6. Mai 2009 und der Einspracheentscheid des Amtes für Industrie, Gewerbe und Arbeit Graubünden vom 8. Januar 2009 werden aufgehoben.
2. Es werden keine Gerichtskosten erhoben.
3. Der Beschwerdegegner hat den Beschwerdeführer für das bundesgerichtliche Verfahren mit Fr. 2'800.- zu entschädigen.
4. Die Sache wird zur Neuverlegung der Parteientschädigung des vorangegangenen Verfahrens an das Verwaltungsgericht des Kantons Graubünden zurückgewiesen.
5. Dieses Urteil wird den Parteien, dem Verwaltungsgericht des Kantons Graubünden und dem Staatssekretariat für Wirtschaft schriftlich mitgeteilt.
Luzern, 22. Dezember 2009
Im Namen der I. sozialrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Die Gerichtsschreiberin:
Ursprung Weber Peter