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.

Das Bundesgericht zieht in Erwägung:
1.- a) Nach Art. 100 Abs. 1 lit. b Ziff. 3 OG ist die Verwaltungsgerichtsbeschwerde auf dem Gebiet der Fremdenpolizei unzulässig gegen die Erteilung oder Verweigerung von Bewilligungen, auf die das Bundesrecht keinen Anspruch einräumt.
Gemäss Art. 4 des Bundesgesetzes vom 26. März 1931 über Aufenthalt und Niederlassung der Ausländer (ANAG; SR 142. 20) entscheidet die zuständige Behörde, im Rahmen der gesetzlichen Vorschriften und der Verträge mit dem Ausland, nach freiem Ermessen über die Bewilligung von Aufenthalt und Niederlassung. Der Ausländer hat damit grundsätzlich keinen Anspruch auf Erteilung bzw. Verlängerung einer Aufenthaltsbewilligung, und die Verwaltungsgerichtsbeschwerde ist ausgeschlossen, soweit er sich nicht auf eine Sondernorm des Bundesrechts oder eines Staatsvertrags berufen kann, die ihm einen Anspruch auf eine solche Bewilligung einräumt (<ref-ruling> E. 1a S. 63; <ref-ruling> E. 2 S. 381; <ref-ruling> E. 1a S. 363 f., je mit Hinweisen).
b) Gemäss Art. 7 ANAG hat der ausländische Ehegatte eines Schweizer Bürgers Anspruch auf Erteilung und Verlängerung der Aufenthaltsbewilligung (Abs. 1 Satz 1); der Anspruch erlischt, wenn ein Ausweisungsgrund vorliegt (Abs. 1 Satz 3). Kein Anspruch besteht, wenn die Ehe eingegangen worden ist, um die Vorschriften über Aufenthalt und Niederlassung von Ausländern und namentlich jene über die Begrenzung der Zahl der Ausländer zu umgehen (Abs. 2). Die Beschwerdeführer sind miteinander verheiratet, und die Ehefrau ist Schweizerin. Sie haben damit grundsätzlich Anspruch auf Erteilung der Aufenthaltsbewilligung (<ref-ruling> E. 1b 292). Diesen könne sie zudem auch aus dem in Art. 8 Ziff. 1 EMRK garantierten Schutz des Familienlebens ableiten, da ihre Ehe gemäss den nicht offensichtlich unzutreffenden und somit für das Bundesgericht grundsätzlich verbindlichen Sachverhaltsfeststellungen der Vorinstanz (Art. 105 Abs. 2 OG) tatsächlich gelebt wird (<ref-ruling> E. 1 S. 8, mit Hinweis). Ob ein Ausweisungsgrund den Anspruch erlöschen lässt, ist eine Frage der materiellen Prüfung (<ref-ruling> E. 1 S. 8; <ref-ruling> E. 3d S. 151). Die Ehefrau ist durch die verweigerte Verlängerung der Aufenthaltsbewilligung ihres Gatten in besonderer Weise berührt und hat ein eigenes schutzwürdiges Interesse an deren Erteilung.
Sie ist daher ebenfalls beschwerdeberechtigt (Art. 103 lit. a OG; vgl. auch <ref-ruling> E. 2b und c S. 187/188 betr. verweigerter Zustimmung zur Verlängerung einer Aufenthaltsbewilligung).
Die rechtzeitig und formrichtig eingereichte Verwaltungsgerichtsbeschwerde erweist sich insoweit als zulässig.
c) Die Verwaltungsgerichtsbeschwerde richtet sich gemäss Art. 98 lit. g OG gegen Verfügungen letzter kantonaler Instanzen. Angefochten werden kann im vorliegenden Verfahren daher einzig der Entscheid des Verwaltungsgerichts.
Soweit die Beschwerdeführer auch die Aufhebung der Entscheide unterer kantonaler Instanzen verlangen, ist auf die Beschwerde nicht einzutreten (vgl. <ref-ruling> E. 1c S. 33; <ref-ruling> E. 1d S. 417, je mit Hinweis).
d) Im Verfahren der Verwaltungsgerichtsbeschwerde kann die Verletzung von Bundesrecht, einschliesslich Überschreitung oder Missbrauch des Ermessens, sowie die unrichtige oder unvollständige Feststellung des rechtserheblichen Sachverhalts gerügt werden (Art. 104 lit. a und lit. b OG).
Hat - wie hier - eine richterliche Behörde als Vorinstanz entschieden, ist das Bundesgericht allerdings an deren Sachverhaltsfeststellung gebunden, sofern diese nicht offensichtlich unrichtig, unvollständig oder unter Verletzung wesentlicher Verfahrensbestimmungen erfolgt ist (Art. 105 Abs. 2 OG). Damit wird die Möglichkeit, vor Bundesgericht Noven vorzubringen, weitgehend eingeschränkt. Das Bundesgericht lässt nur solche neuen Tatsachen und Beweismittel zu, welche die Vorinstanz von Amtes wegen hätte berücksichtigen müssen und deren Nichtbeachtung eine Verletzung wesentlicher Verfahrensvorschriften darstellt (<ref-ruling> 3a S. 421; <ref-ruling> E. 1c S. 99 f., mit Hinweisen).
Der von den Beschwerdeführern eingereichte Bericht des Gemeindeschreibers von Arch vom 28. Mai 2001 ist daher nicht zu berücksichtigen. Unbeachtlich ist auch die zwischenzeitlich eingetretene, mit Schreiben vom 3. Mai 2001 bestätigte Schwangerschaft der Beschwerdeführerin, da sie bereits vor dem kantonalen Verwaltungsgericht hätte geltend gemacht werden können (vgl. Thomas Merkli/Arthur Aeschlimann/Ruth Herzog, Kommentar zum Gesetz vom 23. Mai 1989 über die Verwaltungsrechtspflege des Kantons Bern [VRPG; BSG 155. 21], Rz 17 zu Art. 25).
2.- a) Gemäss Art. 10 Abs. 1 lit. a ANAG kann ein Ausländer aus der Schweiz ausgewiesen werden, wenn er wegen eines Verbrechens oder Vergehens gerichtlich bestraft wurde.
Die Ausweisung darf jedoch nur ausgesprochen werden, wenn sie nach den gesamten Umständen angemessen erscheint (Art. 11 Abs. 3 ANAG). Hierbei sind vor allem die Schwere des Verschuldens des Ausländers, die Dauer seiner Anwesenheit in der Schweiz und die ihm und seiner Familie drohenden Nachteile zu berücksichtigen (Art. 16 Abs. 3 der Vollziehungsverordnung vom 1. März 1949 zum Bundesgesetz über Aufenthalt und Niederlassung der Ausländer [ANAV; SR 142. 201]).
Die Nichterteilung bzw. Nichterneuerung der Aufenthaltsbewilligung an den wegen eines Verbrechens oder Vergehens verurteilten ausländischen Ehegatten eines Schweizer Bürgers setzt ebenfalls eine solche Interessenabwägung voraus (<ref-ruling> E. 4a S. 13). Der Anspruch auf Erteilung der Bewilligung gemäss Art. 7 Abs. 1 ANAG erlischt nicht bereits dann, wenn ein Ausländer wegen eines Verbrechens oder Vergehens verurteilt wurde, sondern nur, wenn auch die Interessenabwägung ergibt, dass die Bewilligung zu verweigern ist (<ref-ruling> E. 4a S. 13, mit Hinweis). Bei der Interessenabwägung müssen dem öffentlichen Interesse, das der Nichtverlängerung der Aufenthaltsbewilligung zugrunde liegt, die privaten Interessen des Beschwerdeführers an seinem weiteren Aufenthalt in der Schweiz gegenüber gestellt werden.
Nicht entscheidend sind dabei der im Rahmen eines Strafverfahrens angeordnete Verzicht auf eine Landesverweisung nach <ref-law> oder deren Aufschub. Sie stehen der fremdenpolizeilichen Ausweisung nach Art. 10 Abs. 1 lit. a ANAG nicht entgegen (125 II 105 E. 2b S. 107 f., mit Hinweisen). Die Beschwerdeführer können folglich aus der Tatsache, dass das Amtsgericht Bucheggberg-Wasseramt im Urteil vom 27. April 1998 auf eine unbedingte Landesverweisung verzichtete bzw.
der Gerichtspräsident 3 des Gerichtskreises III Aarberg-Büren-Erlach am 9. Februar 1999 den damals bedingten Vollzug der Landesverweisung nicht widerrufen hat, nichts ableiten.
b) Der Beschwerdeführer wurde mehrmals zu Gefängnisstrafen verurteilt; deren Dauer beträgt insgesamt mehr als 30 Monate. Damit ist der Ausweisungsgrund von Art. 10 Abs. 1 lit. a ANAG offensichtlich erfüllt (vgl. <ref-ruling> E. 3a S. 524). Hinsichtlich des Verschuldens des Beschwerdeführers ist festzuhalten, dass dieser wegen einer Vielzahl von Delikten verurteilt worden ist und sich - entgegen seinen Beteuerungen in der Verhandlung vom 27. April 1998 vor dem Strafamtsgericht Bucheggberg-Wasseramt - weder durch die bedingt ausgesprochenen Strafen noch durch die im Rahmen der Verfolgung der damals beurteilten Delikte ausgestandene Untersuchungshaft (10. bis 17. Juli 1996) von weiteren Straftaten abhalten liess. Das Verschulden des Beschwerdeführers wiegt umso schwerer, als er mit seiner neuerlichen Tat (Überschreitung der Höchstgeschwindigkeit um 83 km/h begangen am 28. Juni 1998) in einem Rechtsbereich delinquiert hat, in dem er bereits einschlägig vorbestraft war (vgl. Urteil des Amtsgerichts Solothurn Lebern vom 23. Januar 1996). Es besteht somit grundsätzlich ein gewichtiges Interesse daran, den Beschwerdeführer von der Schweiz fernzuhalten. Dass sich der Beschwerdeführer während der von ihm zwischenzeitlich verbüssten Gefängnisstrafe wohl verhielt und seither nicht mehr delinquierte, vermag daran nichts zu ändern, da die seit der bedingten Entlassung aus dem Strafvollzug und dem heutigen Urteil vergangene Zeit zu kurz ist, um ohne weiteres auf eine andauernde Einsicht des Beschwerdeführers zu schliessen. Es stellt sich somit einzig die Frage, ob die privaten Interessen der Beschwerdeführenden an einem Verbleib des Beschwerdeführers in der Schweiz, die öffentlichen Interessen an dessen Fernhaltung überwiegen.
c) aa) Der Beschwerdeführer reiste 1991, kurz vor seinem achtzehnten Geburtstag, nach Abschluss einer Ausbildung zum Elektroinstallateur, in die Schweiz ein. Er ist daher sowohl mit der Sprache als auch den Gepflogenheiten seiner Heimat, in der er fast zwei Drittel seines bisherigen Lebens verbracht hat, bestens vertraut, so dass davon auszugehen ist, dass er sich nach einer Rückkehr dort wieder zurechtfinden würde. In der Schweiz wechselte der Beschwerdeführer demgegenüber während seines Aufenthaltes mehrmals nicht nur den Wohnsitz, sondern auch den Arbeitsplatz. Von einer tiefen Verwurzelung im Gastland kann deshalb kaum gesprochen werden. Daran vermag auch die Tatsache nichts zu ändern, dass zumindest ein Teil seiner Familie ebenfalls in der Schweiz lebt, konnte doch auch sie ihn nicht von den Straftaten abhalten. Auf Grund dieser Umstände ist es dem Beschwerdeführer somit grundsätzlich zuzumuten, in seine Heimat zurückzuziehen, auch wenn eine Rückkehr in das durch den Krieg erschütterte Jugoslawien mit Schwierigkeiten verbunden ist.
bb) Der Beschwerdeführer ist mit der Beschwerdeführerin, einer Schweizer Bürgerin, verheiratet. Diese ist an die Verhältnisse einer intakten schweizerischen Dorfgemeinschaft gewöhnt, spricht weder Serbisch noch Albanisch oder sonst eine Fremdsprache und ist, wie die Beschwerdeführer selber festhalten, kaum ausbildungsfähig. Es ist daher davon auszugehen, dass sie sich in der Heimat des Beschwerdeführers nur äusserst schwer integrieren könnte. Auch die guten Beziehungen, welche die Beschwerdeführerin zu ihren in der Schweiz lebenden Angehörigen unterhält und die ebenfalls vom Beschwerdeführer gepflegt werden, könnten bei einer Ausreise nach Jugoslawien praktisch kaum aufrecht erhalten werden.
Der Beschwerdeführerin ist es folglich kaum zuzumuten, dem Beschwerdeführer in seine Heimat zu folgen (vgl. auch Urteil des Europäischen Gerichtshofes für Menschenrechte vom 2. August 2001 i.S. Boultif [Application no. 54273/00], Rz 53); zumindest ist davon auszugehen, dass ihr dies grosse Probleme bereiten würde. Solche Schwierigkeiten sind bei der Abwägung der berührten gegenläufigen Interessen zu berücksichtigen, sie vermögen jedoch für sich allein betrachtet eine Ausweisung bzw. Nichtverlängerung der Bewilligung nicht ohne weiteres auszuschliessen (vgl. auch Urteil des Europäischen Gerichtshofes für Menschenrechte vom 2. August 2001 i.S. Boultif [Application no. 54273/00], Rz 48 in fine).
Bei der hier vorzunehmenden Interessenabwägung fällt eine Tatsache besonders ins Gewicht: Die auf Grund der Akten erstellte Teilnahme der Beschwerdeführerin als Zuhörerin an der Verhandlung vor dem Strafamtsgericht Bucheggberg-Wasseramt vom 27. April 1998. Anlässlich dieser Verhandlung kamen nicht nur die bereits früher begangenen Delikte des Beschwerdeführers zur Sprache, vielmehr befand das Gericht auch über die Ausfällung einer Landesverweisung, die in der Folge für die Dauer von 5 Jahren bedingt ausgesprochen wurde. Entgegen den Ausführungen in der Beschwerde musste daher der Beschwerdeführerin bereits vor ihrer Heirat mit dem Beschwerdeführer bewusst gewesen sein, dass ein weiteres Fehlverhalten des Beschwerdeführers fremdenpolizeiliche Konsequenzen, bis hin zu dessen Ausweisung, nach sich ziehen konnte. Als sie am 12. Juni 1998 den Beschwerdeführer heiratete, hat die Beschwerdeführerin es daher in Kauf genommen, ihre Ehe unter Umständen nicht in der Schweiz leben zu können.
Dass die Behörden des Kantons Bern dem Beschwerdeführer auf Grund der Eheschliessung die Aufenthaltsbewilligung vorerst verlängerten, vermag daran nichts zu ändern, zumal das Strafurteil vom 27. April 1998 damals noch nicht rechtskräftig war.
d) Unter diesen Umständen geht im vorliegenden Fall das öffentliche Interesse, den Beschwerdeführer von der Schweiz fernzuhalten (vgl. vorangehende E. 2b), den privaten Interessen an einem Verbleib des Beschwerdeführers in der Schweiz vor. Die in Art. 7 Abs. 1 in Verbindung mit Art. 10 Abs. 1 ANAG gesetzlich vorgesehene Nichtverlängerung der Aufenthaltsbewilligung des Beschwerdeführers erweist sich somit als verhältnismässig.
3.- a) Die Verwaltungsgerichtsbeschwerde ist demnach unbegründet.
b) Die Beschwerdeführer haben um Gewährung der unentgeltlichen Rechtspflege und um Verbeiständung für das vorliegende Verfahren ersucht. Sie sind offensichtlich bedürftig, und die von ihnen gestellten Rechtsbegehren können nicht als von vornherein aussichtslos bezeichnet werden (Art. 152 Abs. 1 OG). Zudem rechtfertigt sich der Beizug eines Rechtsanwaltes (Art. 152 Abs. 2 OG). Dem Gesuch ist daher zu entsprechen.
Damit sind keine Kosten zu erheben (Art. 152 Abs. 1 OG) und der Rechtsvertreter der Beschwerdeführer ist für das bundesgerichtliche Verfahren aus der Bundesgerichtskasse zu entschädigen (Art. 152 Abs. 2 OG).

Demnach erkennt das Bundesgericht:
1.- Die Verwaltungsgerichtsbeschwerde wird abgewiesen, soweit darauf einzutreten ist.
2.- Den Beschwerdeführern wird die unentgeltliche Rechtspflege gewährt.
a) Es werden keine Kosten erhoben.
b) Prof. Dr. iur. Jürg Brühwiler wird als unentgeltlicher Rechtsbeistand der Beschwerdeführer bestellt, und es wird ihm für das bundesgerichtliche Verfahren aus der Bundesgerichtskasse ein Honorar von Fr. 1'500.-- ausgerichtet.
3.- Dieses Urteil wird den Beschwerdeführern, der Polizei- und Militärdirektion sowie dem Verwaltungsgericht des Kantons Bern und dem Bundesamt für Ausländerfragen schriftlich mitgeteilt.
_
Lausanne, 22. August 2001
Im Namen der II. öffentlichrechtlichen Abteilung
des SCHWEIZERISCHEN BUNDESGERICHTS
Der Präsident: Die Gerichtsschreiberin: