Ausweisung, hat sich ergeben: A.- Der am 2. April 1976 geborene jugoslawische Staatsangehörige M._ gelangte am 25. Januar 1991 erstmals in die Schweiz und wurde in die Niederlassungsbewilligung seiner Mutter einbezogen. Am 21. April 1997 wurde M._ bei einem Einbruchsdiebstahl auf frischer Tat ergriffen und bis zum 7. Mai 1997 in Untersuchungshaft genommen. Kurz darauf reiste er nach Jugoslawien aus, wo er gemäss einer Bestätigung des jugoslawischen Generalkonsulats ab dem 10. Juni 1997 einen einjährigen Militärdienst leisten musste. Das Kreisgericht Chur verurteilte am 30. Oktober 1997 M._ in Abwesenheit wegen mehrfachen vollendeten und versuchten Diebstahls, mehrfachen Hausfriedensbruchs und Sachbeschädigung sowie wegen Entwendung eines Fahrzeuges zum Gebrauch zu sechs Monaten Gefängnis und drei Jahren Landesverweisung; für die Freiheitsstrafe wurde, bei einer dreijährigen Probezeit, der bedingte Strafvollzug gewährt. Der Beschwerdeführer stellte hiergegen ein Restitutionsgesuch, über das bislang nicht entschieden wurde. B.- Die Fremdenpolizei des Kantons Graubünden stellte mit Verfügung vom 28. Mai 1998 fest, dass die Niederlassungsbewilligung von M._ erloschen sei, weil er sich mehr als sechs Monate im Ausland aufgehalten und es unterlassen habe, ein Gesuch um Aufrechterhaltung der Niederlassungsbewilligung zu stellen. Das Verwaltungsgericht des Kantons Graubünden (im Folgenden: Verwaltungsgericht) hiess das dagegen durch M._ erhobene Rechtsmittel am 17. November 1998 mit der Begründung gut, die Niederlassungsbewilligung sei nicht erloschen, da sich M._ auf den Vertrauensgrundsatz berufen könne; ob er durch sein strafrechtlich relevantes Verhalten einen Ausweisungsgrund gesetzt habe, müsse die Fremdenpolizei in einem anschliessenden neuen Verfahren prüfen. C.- Mit Verfügung vom 4. Mai 1999 wies die Fremdenpolizei des Kantons Graubünden M._ für eine unbestimmte Zeit aus der Schweiz aus. Die von M._ hiegegen eingereichte Beschwerde wurde vom Justiz-, Polizei- und Sanitätsdepartement des Kantons Graubünden am 7. Juli 1999 und der gegen diesen Entscheid erhobene Rekurs vom Verwaltungsgericht am 8. Oktober 1999 abgewiesen. Einzig dem Antrag auf Gewährung der unentgeltlichen Rechtspflege für das Beschwerde- und das Rekursverfahren gab das Verwaltungsgericht statt. D.- M._ hat am 4. Februar 2000 Verwaltungsgerichtsbeschwerde beim Bundesgericht eingereicht mit dem Antrag, das Urteil des Verwaltungsgerichts vom 8. Oktober 1999 aufzuheben, ihm die Niederlassungsbewilligung zu erteilen und von einer Ausweisung abzusehen. Im Übrigen ersucht er für das bundesgerichtliche Verfahren um unentgeltliche Rechtspflege und Verbeiständung. Das Justiz-, Polizei- und Sanitätsdepartement des Kantons Graubünden sowie das Bundesamt für Ausländerfragen (im Auftrag des Eidgenössischen Justiz- und Polizeidepartements) schliessen auf Abweisung der Verwaltungsgerichtsbeschwerde. Das Verwaltungsgericht des Kantons Graubünden beantragt Abweisung, soweit auf die Beschwerde eingetreten werde. E.- Der Präsident der II. öffentlichrechtlichen Abteilung hat das mit der Beschwerde verbundene Gesuch um aufschiebende Wirkung am 28. Februar 2000 abgewiesen.