Nichterneuerung der Aufenthaltsbewilligung, hat sich ergeben: A.- Der jugoslawische Staatsangehörige A.B._, geb. 1973, reiste am 18. Februar 1991 im Rahmen des Familiennachzuges zu seinem in Selzach (Kanton Solothurn) lebenden Vater in die Schweiz ein. Am 23. Juli 1991 erhielt er eine Aufenthaltsbewilligung B. In der Folge wechselte er mehrmals den Aufenthaltskanton; dabei kam es zu mehreren Verstössen gegen die Ausländergesetzgebung. In den Jahren 1994 bis 1998 wurde A.B._ auch verschiedene Male strafrechtlich verurteilt: - Urteil des Gerichtspräsidenten von SolothurnLebern vom 19. August 1994: Busse von Fr. 250.-- wegen Widerhandlung gegen das Strassenverkehrsgesetz. - Urteil des Tribunal de police du district de Neuchâtel vom 25. Oktober 1994: 10 Tage Gefängnis bedingt (Probezeit zwei Jahre) wegen einfacher Körperverletzung. - Urteil des Amtsgerichts Solothurn Lebern vom 23. Januar 1996: 12 Monate Gefängnis bedingt (Probezeit drei Jahre) und Busse von Fr. 3'000.-- wegen fahrlässiger Tötung und grober Verletzung von Verkehrsregeln. - Urteil des Amtsstatthalters von Luzern-Stadt vom 10. März 1998: 5 Wochen Gefängnis bedingt (Probezeit zwei Jahre) wegen Veruntreuung. - Urteil des Strafamtsgerichts Bucheggberg-Wasseramt vom 27. April 1998: 12 Monate Gefängnis bedingt (Probezeit drei Jahre) und 5 Jahre Landesverweisung bedingt (Probezeit 3 Jahre) wegen einfachen Diebstahls, gewerbs- und mehrfachen bandenmässigen Diebstahls sowie mehrfacher Sachbeschädigung (begangen in der Zeit vom 13. Juni 1996 bis 10. Juli 1996). Widerruf des am 25. Oktober 1994 und am 23. Januar 1996 gewährten bedingten Strafvollzuges. Mit Verfügung vom 28. Juli 1997 hatte es der Kanton Luzern abgelehnt, die Aufenthaltsbewilligung von A.B._ zu verlängern, und diesen verpflichtet, das Kantonsgebiet bis spätestens 15. September 1997 zu verlassen. Das Bundesamt für Ausländerfragen dehnte die Wegweisung am 9. Januar 1998 auf das ganze Gebiet der Schweiz aus und setzte A.B._ eine Frist zur Ausreise bis spätestens 30. Januar 1998. Die Verfügungen wurden angefochten. B.- Am 12. Juni 1998 heiratete A.B._ in S._ die Schweizerbürgerin B.W._ und zog zu ihr nach A._ (Kanton Bern). Gestützt darauf erhielt er vom Kanton Bern eine Aufenthaltsbewilligung B. Am 9. Februar 1999 verurteilte der Gerichtspräsident 3 des Gerichtskreises III Aarberg-Büren-Erlach A.B._ wegen grober Verkehrsregelverletzung durch Überschreiten der signalisierten Höchstgeschwindigkeit um 83 km/h, begangen am 28. Juni 1998, zu fünf Monaten Gefängnis unbedingt. Am 5. Juli 1999 trat A.B._ seine Strafen in der solothurnischen Strafanstalt Schöngrün an. Mit Schreiben vom 29. September 1999 verfügte das Amt für Polizeiverwaltung der Polizei- und Militärdirektion des Kantons Bern die Nichterneuerung der auf den 18. Februar 2000 ablaufenden Aufenthaltsbewilligung. Die Ausreisefrist wurde auf den Tag des Bewilligungsablaufs bzw. der Entlassung aus dem Strafvollzug festgesetzt. Am 22. Juni 2000 wies die Polizei- und Militärdirektorin des Kantons Bern die gegen diesen Entscheid gerichtete Beschwerde von A.B._ ab. Am 20. Juli 2000 wurde A.B._ wegen guten Verhaltens bedingt aus dem Strafvollzug entlassen. Das Verwaltungsgericht des Kantons Bern bestätigte den Entscheid der Polizei- und Militärdirektorin des Kantons Bern vom 22. Juni 2000 mit Urteil vom 25. April 2001. C.- Hierauf haben A.B._ und B.B._ am 30. Mai 2001 beim Bundesgericht Verwaltungsgerichtsbeschwerde eingereicht, mit folgenden Rechtsbegehren: "1.Die Verfügung der Fremdenpolizei des Kantons Bern vom 29. September 1999, der Entscheid der Polizei- und Militärdirektion des Kantons Bern vom 22. Juni 2000 und das Urteil des Verwaltungsgerichts des Kantons Bern vom 25. April 2001 seien aufzuheben. 2. Die am 18. Februar 2000 abgelaufene Aufenthaltsbewilligung des A.B._ sei zu erneuern. 3. Der vorliegenden Beschwerde sei aufschiebende Wirkung zuzuerkennen. 4. Den Beschwerdeführern sei auch für das Verfahren vor Bundesgericht die unentgeltliche Rechtspflege zu bewilligen unter Beiordnung des unterzeichneten Anwalts als Rechtsbeistand. Unter Kosten und Entschädigungsfolgen.. " D.- Das Verwaltungsgericht und die Polizei- und Militärdirektion des Kantons Bern beantragen, die Beschwerde abzuweisen; bezüglich des Gesuches um aufschiebende Wirkung enthalten sie sich eines Antrages. Das Bundesamt für Ausländerfragen schliesst auf Abweisung der Beschwerde. E.-Mit Verfügung vom 15. Juni 2001 hat der Präsident der II. öffentlichrechtlichen Abteilung der Verwaltungsgerichtsbeschwerde die aufschiebende Wirkung zuerkannt.