Sachverhalt:
A. Der 1950 geborene K._ war bis Januar 2008 an verschiedenen Stellen als Arbeitnehmer tätig. Von Februar bis Oktober 2008 betrieb er in der Gemeinde X._ als selbstständig Erwerbender einen mobilen Imbisswagen. Nachdem ihm die Gemeinde die notwendige Bewilligung für den Betrieb am vorgesehenen Standort nicht erteilte und am 23. Juli 2008 eine Schliessung des Imbisswagens bis 31. Oktober 2008 verfügt hatte, stellte K._ am 13. Oktober 2008 (Eingang) bei der Arbeitslosenkasse Graubünden einen Antrag auf Arbeitslosenentschädigung ab 10. Oktober 2008. Am 14. November 2008 unterzeichnete er mit Wirkung ab 1. Januar 2009 einen Pachtvertrag für das Restaurant Y._. Mit Verfügung vom 2. Dezember 2008 lehnte das Amt für Industrie, Gewerbe und Arbeit Graubünden (KIGA) den Antrag auf Arbeitslosenentschädigung wegen fehlender Vermittlungsfähigkeit ab. Im Einspracheentscheid vom 9. Januar 2009 bestätigte es ihre Verfügung.
B. Die hiegegen eingereichte Beschwerde wies das Verwaltungsgericht des Kantons Graubünden mit Entscheid vom 19. Mai 2009 ab. Ein Gesuch um unentgeltliche Rechtspflege wies es wegen Aussichtslosigkeit der Beschwerde ebenfalls ab.
C. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten lässt K._ die Aufhebung des vorinstanzlichen Entscheides, die Ausrichtung von Arbeitslosenentschädigung vom 10. Oktober bis 31. Dezember 2008 und die Gewährung der unentgeltlichen Rechtspflege im vorinstanzlichen Verfahren beantragen. Ferner wird um unentgeltliche Prozessführung und Verbeiständung im Verfahren vor Bundesgericht ersucht.
Das KIGA und das Staatssekretariat für Wirtschaft verzichten auf eine Vernehmlassung.

Erwägungen:
1. 1.1 Im verwaltungsgerichtlichen Beschwerdeverfahren sind grundsätzlich nur Rechtsverhältnisse zu überprüfen und zu beurteilen, zu denen die zuständige Verwaltungsbehörde vorgängig verbindlich - in Form einer Verfügung - Stellung genommen hat. Insoweit bestimmt die Verfügung den beschwerdeweise weiterziehbaren Anfechtungsgegenstand. Umgekehrt fehlt es an einem Anfechtungsgegenstand und somit an einer Sachurteilsvoraussetzung, wenn und insoweit keine Verfügung ergangen ist (<ref-ruling> E. 2.1, 125 V 413 E. 1a S. 414 mit Hinweisen). Streitgegenstand im System der nachträglichen Verwaltungsrechtspflege ist das Rechtsverhältnis, welches - im Rahmen des durch die Verfügung bestimmten Anfechtungsgegenstandes - den auf Grund der Beschwerdebegehren effektiv angefochtenen Verfügungsgegenstand bildet. Anfechtungs- und Streitgegenstand sind danach identisch, wenn die Verwaltungsverfügung insgesamt angefochten wird; bezieht sich demgegenüber die Beschwerde nur auf einzelne der durch die Verfügung bestimmten Rechtsverhältnisse, gehören die nicht beanstandeten - verfügungsweise festgelegten - Rechtsverhältnisse zwar wohl zum Anfechtungs-, nicht aber zum Streitgegenstand (<ref-ruling> E. 2.1, 125 V 413 E. 1b).
1.2 In der Verfügung vom 2. Dezember 2008 verneinte die Beschwerdegegnerin einen Anspruch auf Arbeitslosenversicherung wegen fehlender Vermittlungsfähigkeit. Mit Eingabe vom 3. Dezember 2008 (persönlich abgegeben am 4. Dezember 2008) wurde Einsprache erhoben und eine vorhandene Vermittlungsbereitschaft geltend gemacht. Am 4. Dezember 2008 reichte der Beschwerdeführer mit separater Eingabe sodann ein Gesuch um Taggelder zur Förderung der selbstständigen Erwerbstätigkeit im Sinne von <ref-law> ein. Mit Entscheid vom 5. Dezember 2008 wies die Beschwerdegegnerin dieses Gesuch ab. Gegenstand des Einspracheentscheids vom 9. Januar 2009 entsprechend den Vorbringen der Einsprache vom 3. Dezember 2008 war lediglich die Vermittelbarkeit des Beschwerdeführers. Soweit der Beschwerdeführer im vorinstanzlichen Verfahren und in seiner Beschwerde in öffentlich-rechtlichen Angelegenheiten vor Bundesgericht nun die Ausrichtung von Taggeldern zur Förderung der selbstständigen Erwerbstätigkeit im Sinne von <ref-law> geltend macht und die Abweisung des Gesuchs vom 5. Dezember 2008 rügt, fehlt es an einem Anfechtungsgegenstand. Aufgrund der fehlenden Einsprache gegen die Abweisung des Gesuchs vom 5. Dezember 2008 hat sich die Beschwerdegegnerin im Einspracheentscheid dazu nicht geäussert. Auf die Beschwerde ist in diesem Punkt somit nicht einzutreten.
2. Die Beschwerde in öffentlich-rechtlichen Angelegenheiten (<ref-law>) kann wegen Rechtsverletzung gemäss Art. 95 f. BGG erhoben werden. Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat (<ref-law>), und 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>).
3. Das kantonale Gericht hat die Bestimmungen, über die für den Anspruch auf Arbeitslosenentschädigung vorausgesetzte Vermittlungsfähigkeit (<ref-law>) und die dazu ergangene Rechtsprechung, insbesondere bezüglich der Vermittlungsbereitschaft als Teilgehalt der Vermittlungsfähigkeit (<ref-ruling> E. 6a S. 58), sowie die der versicherten Person obliegenden Schadenminderungspflicht (<ref-law>) zutreffend dargelegt. Darauf wird verwiesen.
Mit der gesetzlichen Schadenminderungspflicht ist es zu vereinbaren, dass ein Arbeitsloser sich auch um Möglichkeiten zum Aufbau einer selbstständigen Tätigkeit umsieht. Unterlässt er es aber im Hinblick auf dieses Ziel, sich daneben auch in vertretbarem Umfang um eine unselbstständige Erwerbstätigkeit zu bemühen, liegt Vermittlungsunfähigkeit vor, welche den Anspruch auf Arbeitslosenentschädigung ausschliesst (ARV 2002 S. 55, C 353/00 E. 2b).
4. Streitig und zu prüfen ist der Anspruch des Beschwerdeführers auf Arbeitslosenentschädigung vom 10. Oktober bis 31. Dezember 2008. Die Vorinstanz verneinte einen solchen, weil beim Beschwerdeführer die subjektive Vermittlungsfähigkeit nicht vorhanden gewesen sei. Er habe offensichtlich kein ernsthaftes Interesse an einer unselbstständigen Erwerbstätigkeit gehabt. Vielmehr habe er während der ganzen Zeit der Arbeitslosigkeit seinen Fokus auf die Fortsetzung der selbstständigen Erwerbstätigkeit gerichtet. Der Beschwerdeführer macht hingegen im Wesentlichen geltend, er habe sich auch um unselbstständige Stellen bemüht. Seine Vermittlungsfähigkeit sei daher zu bejahen.
5. 5.1 Bei andauernd selbstständig erwerbenden Personen ist zunächst zu berücksichtigen, dass diese in der Regel bereits von vornherein vom Arbeitslosentaggeldbezug ausgeschlossen sind. Unter dem Gesichtspunkt der rechtsmissbräuchlichen Gesetzesumgehung ist dabei rechtsprechungsgemäss massgebend, ob der Status des Selbstständigerwerbenden mit dem Ziel dauernder wirtschaftlicher und unternehmerischer Unabhängigkeit aufgenommen und beibehalten wird (Urteil C 9/05 vom 21. Dezember 2005 E. 2.3). Wichtiger Umstand hierbei ist, ob die Person das letzte Arbeitnehmerverhältnis selber gekündigt hat mit dem Ziel sich selbstständig zu machen, oder unfreiwillig aus diesem ausgeschieden ist und durch die Aufnahme einer selbstständigen Erwerbstätigkeit eine Anmeldung bei der Arbeitslosenversicherung zu vermeiden versuchte. Nur letzteres rechtfertigt es, die Anmeldung zum Bezug von Arbeitslosentaggeldern unter dem Gesichtspunkt der Vermittlungsfähigkeit zu prüfen (Urteile 8C_79/2009 vom 25. September 2009 E. 4 und 8C_81/2009 vom 27. August 2009 E. 3.3 und 3.4; je mit Hinweisen).
5.2 Aus den vorhandenen Akten lassen sich diese Punkte, insbesondere die näheren Umstände der Beendigung der letzten unselbstständigen Arbeitsstelle des Beschwerdeführers nicht eindeutig beantworten. Diese können vorliegend allerdings offen gelassen werden, da die Vermittlungsfähigkeit bzw. die Vermittlungsbereitschaft ohnehin zu verneinen ist, wie die folgenden Ausführungen zeigen.
6. Der Beschwerdeführer betrieb als selbstständig Erwerbender ab 1. Februar 2008 in der Gemeinde X._ einen Imbisswagen. Am 23. Juli 2008 lehnte die Gemeinde das für den Betrieb des Imbisswagens notwendige Baugesuch ab und setzte eine Frist bis 31. Oktober 2008 an, um diesen zu schliessen. Von Ende Juli bis zu Beginn des Monats September 2008 suchte der Beschwerdeführer intensiv, jedoch erfolglos einen neuen Stellplatz für seinen Imbisswagen (insgesamt 16 Anfragen). Ab Mitte September bis Ende Oktober gab er auf den Nachweisformularen für die persönlichen Arbeitsbemühungen 14 Bewerbungen im Zusammenhang mit zur Pacht vorgesehenen Lokalitäten an, hauptsächlich im Bereich Gastronomie, vereinzelt auch für Ladenlokale. Seine Anfrage in den Bewerbungen lautete zwar jeweils, ob man bereit wäre, ihn auch im Angestelltenverhältnis als Geschäftsführer zu verpflichten. Wie die Vorinstanz korrekt festgehalten hat, können hierin allerdings keine ernsthaften Stellenbewerbungen für unselbstständige Stellen gesehen werden. Es handelte sich um zur Pacht vorgesehene Objekte. Als Bewerbungen für tatsächlich unselbstständige Stellen in den Monaten August bis Oktober 2008 gab der Beschwerdeführer lediglich eine sehr kurze Anfrage per Email als Treuhandsachbearbeiter bei der S._ AG und eine mündliche Anfrage als Immobiliensachbearbeiter beim Unternehmen Steiger Treuhand an. Von einem ernsthaften Interesse an einer unselbstständigen Erwerbstätigkeit kann hierbei insgesamt nicht gesprochen werden. Der Beschwerdeführer war in erster Linie an der Weiterführung seiner selbstständigen Tätigkeit bzw. Aufnahme einer neuen selbstständigen Erwerbstätigkeit und nicht am Finden einer Anstellung interessiert. Am 10. Oktober 2008 stellte der Beschwerdeführer den Betrieb seines Imbissladens ein. In seiner Anmeldung für Arbeitslosenentschädigung vom 13. Oktober 2008 gab er an, es liege eine vorübergehende Aufgabe seiner selbstständigen Erwerbstätigkeit in Folge Schliessung des Standortes für den Imbisswagen vor. Sobald er einen neuen Platz gefunden habe, werde er diesen wiedereröffnen und seine selbstständige Tätigkeit weiterbetreiben. Auf Nachfrage der Arbeitslosenkasse Graubünden nach einer Bewilligung für einen neuen Standort und der Wiederaufnahme seiner selbstständigen Tätigkeit, antwortete er am 30. Oktober 2008, er sei noch auf der Suche nach einem geeigneten Standort und könne daher noch keine definitive Zusage machen. Allerdings nahm er bereits im Oktober 2008 Gespräche mit der Verpächterin des Restaurant Y._ auf. Diese Verhandlungen zogen sich bis Mitte November 2008 hin. Am 14. November 2008 unterzeichnete er den Pachtvertrag für das Restaurant Y._, nachdem er eine einheimische Brauerei gefunden hatte, welche bereit war, ihm ein für die Pacht notwendiges Darlehen zu gewähren. Vom 2. November 2008 bis zur Aufnahme der selbstständigen Erwerbstätigkeit als Pächter am 1. Januar 2009 war der Beschwerdeführer als angestellter Marktfahrer befristet beim Unternehmen Walliser Sonnenhüte tätig. Auf dem Nachweisformular für persönliche Arbeitsbemühungen für November 2008 gab der Beschwerdeführer schliesslich noch sechs Bewerbungen für unselbstständige Stellen an. Bemerkenswert ist dabei, dass er bei den schriftlichen Bewerbungen den Anschreiben jeweils keinen Lebenslauf mehr beilegte und bei allen ausdrücklich angab "er sei schon einige Zeit raus". Auch in den Bewerbungen als "Mitarbeiter Küche, Service" bei der Firma M._ und als "Mitarbeiter Diverses" beim Restaurant Z._ gab er dies an, obwohl er effektiv einen Imbisswagen betrieb und somit bereits in der entsprechenden Branche tätig war. Der Beschwerdeführer lässt einwenden, bei der Stellenausschreibung der A._ AG sei ein Sachbearbeiter mit technischer Grundausbildung gesucht worden, wofür er mit seiner Ausbildung als Elektromechaniker ohne weiteres das nötige Rüstzeug mitgebracht hätte, was sich aus seinem Lebenslauf ergebe. In seinem Anschreiben verwies er jedoch lediglich auf seine kaufmännische Ausbildung und legte keinen Lebenslauf bei. Die Bewerbungen im November 2008 können damit - in Übereinstimmung mit der Beurteilung der Vorinstanz - ebenfalls nicht als ernsthafte Stellenbewerbungen betrachtet werden. In umfassender Würdigung der Situation kam die Vorinstanz zum Schluss, der Beschwerdeführer habe kein ernsthaftes Interesse gezeigt an einer unselbstständigen Erwerbstätigkeit. Die subjektive Vermittlungsfähigkeit sei damit zu verneinen. Diese Beurteilung erweist sich als rechtens. Nach dem Gesagten ergibt sich, dass die Absichten und das gesamte Verhalten des Beschwerdeführers auf eine selbstständige Erwerbstätigkeit gerichtet waren. Die Beschwerde ist demgemäss abzuweisen.
7. 7.1 Die Vorinstanz wies das Gesuch des Beschwerdeführers um unentgeltliche Rechtspflege wegen Aussichtslosigkeit der Beschwerde ab.
Gemäss <ref-law> wird im kantonalen Beschwerdeverfahren der Beschwerde führenden Person, wo es die Verhältnisse rechtfertigen, ein "unentgeltlicher Rechtsbeistand" bewilligt. Der Anspruch auf unentgeltliche Verbeiständung setzt die Bedürftigkeit der gesuchstellenden Partei, die fehlende Aussichtslosigkeit der Rechtsbegehren sowie die sachliche Gebotenheit des Beizugs eines Anwalts voraus (Urteil 9C_165/2008 vom 7. August 2008 E. 1.1 mit Hinweisen). Prozessbegehren sind als aussichtslos anzusehen, wenn die Gewinnaussichten beträchtlich geringer sind als die Verlustgefahren, so dass sie kaum als ernsthaft bezeichnet werden können. Massgebend ist, ob eine Partei, die über die nötigen finanziellen Mittel verfügt, sich bei vernünftiger Überlegung zu einem Prozess entschliessen würde. Ob im Einzelfall genügend Erfolgsaussichten bestehen, beurteilt sich nach den Verhältnissen zur Zeit, in der das Gesuch um unentgeltliche Rechtspflege gestellt wird. Wie es sich damit verhält, prüft das Bundesgericht in rechtlicher Hinsicht mit freier Kognition (<ref-ruling> E. 2.3.1 S. 135; <ref-ruling> E. 2.5.3 S. 236).
7.2 Mit Beschwerde vom 10. Februar 2009 vor Vorinstanz reichte der Beschwerdeführer ein Gesuch um unentgeltliche Rechtspflege ein. Angesichts der zahlreichen Einträge auf den Nachweisformularen über die persönlichen Arbeitsbemühungen, unter denen sich zumindest vordergründig auch einige für unselbstständige Arbeitstätigkeiten befanden, erschien das Verfahren nicht zum Vornherein als aussichtslos. Auch die übrigen Voraussetzungen des Anspruchs auf unentgeltliche Verbeiständung (sachliche Gebotenheit des Beizugs eines Anwalts und Bedürftigkeit der gesuchstellenden Person) sind ausgewiesen. Der Beschwerdeführer hat Anspruch auf unentgeltliche Verbeiständung im kantonalen Verfahren. Die Beschwerde ist daher bezüglich der unentgeltlichen Verbeiständung für das vorinstanzliche Verfahren gutzuheissen und die Sache zur Festsetzung der Entschädigung an das kantonale Gericht zurückzuweisen.
8. 8.1 In der Hauptsache sind die Gerichtskosten dem Beschwerdeführer als unterliegende Partei aufzuerlegen (<ref-law>).
Die Überprüfungsbefugnis des Bundesgericht ist bei Sachverhaltsfeststellungen auf offensichtlich unrichtige oder auf Rechtsverletzung beruhende Feststellungen beschränkt (vgl. E. 2). Unter Berücksichtigung dieser beschränkten Kognition erweisen sich die Begehren im Verfahren vor Bundesgericht - anders als im kantonalen Verfahren - als aussichtslos. Dem Gesuch um unentgeltliche Rechtspflege für das bundesgerichtliche Verfahren kann daher nicht entsprochen werden (<ref-law>).
8.2 Entsprechend seinem Ausgang sind im Beschwerdeverfahren um die unentgeltliche Verbeiständung für das vorinstanzliche Verfahren keine Kosten zu erheben (<ref-law>). Der Kanton Graubünden hat den Beschwerdeführer für das bundesgerichtliche Verfahren mit Fr. 700.- zu entschädigen (vgl. Urteile 8C_89/2007 vom 20. August 2008 und 5A_368/2007 vom 18. September 2007).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird teilweise gutgeheissen. Ziffer 2 des Entscheides des Verwaltungsgerichts des Kantons Graubünden vom 19. Mai 2009 wird aufgehoben. Rechtsanwalt lic. iur. Marc Breitenmoser wird als unentgeltlicher Anwalt des Beschwerdeführers für das vorinstanzliche Verfahren bestellt. Die Sache wird zur Festsetzung seiner Entschädigung an die Vorinstanz zurückgewiesen. Im Übrigen wird die Beschwerde abgewiesen, soweit darauf einzutreten ist.
2. Das Gesuch um unentgeltliche Rechtspflege wird abgewiesen.
3. Die Gerichtskosten von Fr. 500.- werden dem Beschwerdeführer auferlegt.
4. Der Kanton Graubünden hat den Beschwerdeführer für das bundesgerichtliche Verfahren mit Fr. 700.- zu entschädigen.
5. Dieses Urteil wird den Parteien, dem Verwaltungsgericht des Kantons Graubünden und dem Staatssekretariat für Wirtschaft schriftlich mitgeteilt.
Luzern, 9. Dezember 2009
Im Namen der I. sozialrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Das präsidierende Mitglied: Der Gerichtsschreiber:
Frésard Kathriner