Erwägungen:
1.
Der 1983 geborene mazedonische Staatsangehörige A.A._ reiste 1998 im Alter von 15 1⁄2 Jahren im Rahmen des Familiennachzugs in die Schweiz ein, wo ihm die Niederlassungsbewilligung erteilt wurde. Am 7. September 2013 heiratete er seine Landsfrau B.A._, welche am 10. Mai 2014 in die Schweiz einreiste und hier aufgrund der geschlossenen Ehe eine Aufenthaltsbewilligung erhielt. Am 6. Dezember 2014 wurde eine gemeinsame Tochter geboren.
A.A._ wurde in der Schweiz mehrfach und in erheblichem Ausmass straffällig:
- Mit Strafbefehl der Staatsanwaltschaft Winterthur/Unterland vom 23. August 2006 wurde er wegen grober Verletzung der Verkehrsregeln zu einer Gefängnisstrafe von 14 Tagen sowie zu einer Busse von Fr. 1'200.-- verurteilt;
- Mit Strafbefehl der Staatsanwaltschaft See/Oberland vom 10. Oktober 2007 wurde er der mehrfachen, teilweise groben Verletzung von Verkehrsregeln schuldig erklärt und zu 360 Stunden gemeinnütziger Arbeit sowie zu einer Busse von Fr. 200.-- verurteilt;
- Mit Strafbefehl der Staatsanwaltschaft See/Oberland vom 1. Juli 2008 wurde er des mehrfachen Führens eines Motorfahrzeugs trotz Entzugs des Führerausweises schuldig erklärt und mit einer Geldstrafe von 90 Tagessätzen bestraft;
- Mit Strafbefehl des Procuratore Pubblico des Kantons Tessin vom 24. September 2008 wurde er abermals wegen Fahrens trotz Entzugs des Führerausweises verurteilt und mit einer Geldstrafe von 75 Tagessätzen sowie mit einer Busse von Fr. 500.-- bestraft;
- Mit Strafbescheid der Staatsanwaltschaft des Kantons St. Gallen, Untersuchungsamt Uznach, vom 27. Oktober 2008 wurde er der mehrfachen Nötigung sowie des mehrfachen Hausfriedensbruchs schuldig erklärt und zu einer Geldstrafe von 20 Tagessätzen sowie zu einer Busse von Fr. 500.-- verurteilt;
- Mit Strafbescheid der Staatsanwaltschaft des Kantons St. Gallen, Untersuchungsamt Uznach, vom 14. Juli 2010 wurde er wegen Entwendung eines Motorfahrzeugs zum Gebrauch sowie des Fahrens trotz Entzugs des Führerausweises zu einer Freiheitsstrafe von 6 Monaten verurteilt;
- Mit Strafbefehl der Staatsanwaltschaft IV des Kantons Zürich vom 24. Oktober 2012 wurde er der versuchten Nötigung, des Missbrauchs einer Fernmeldeanlage sowie des mehrfachen Ungehorsams gegen eine amtliche Verfügung schuldig erklärt und zu einer Geldstrafe von 90 Tagessätzen sowie zu einer Busse von Fr. 1'500.-- verurteilt;
- Schliesslich wurde A.A._ mit Urteil des Obergerichts des Kantons Zürich vom 1. Oktober 2013 wegen Freiheitsberaubung, unrechtmässiger Aneignung, Verleumdung, mehrfacher Drohung, mehrfacher versuchter Nötigung, Beschimpfung, mehrfachem Missbrauch einer Fernmeldeanlage, Entwendung eines Motorfahrzeugs zum Gebrauch sowie Fahrens trotz Entzugs des Führerausweises zu einer Freiheitsstrafe von 27 Monaten, einer Geldstrafe von 30 Tagessätzen sowie zu einer Busse von Fr. 500.-- verurteilt. Das Obergericht lehnte es zudem ab, den Vollzug der Freiheitsstrafe zugunsten einer ebenfalls angeordneten ambulanten Behandlung aufzuschieben, was vom Bundesgericht mit Urteil 6B_95/2014 vom 16. Oktober 2014 bestätigt wurde.
Das Migrationsamt des Kantons Zürich hatte A.A._ bereits mit Verfügungen vom 13. September 2006 sowie vom 22. Januar 2008 verwarnt und für den Fall weiterer Delinquenz schwerer wiegende ausländerrechtliche Massnahmen in Aussicht gestellt.
Mit Verfügung vom 4. Juni 2015 widerrief das kantonale Migrationsamt schliesslich die Niederlassungsbewilligung von A.A._ und es wies das Gesuch von B.A._ um Verlängerung der Aufenthaltsbewilligung ab. Die von den Betroffenen hiergegen ergriffenen Rechtsmittel wurden kantonal letztinstanzlich mit Urteil des Verwaltungsgerichts des Kantons Zürich vom 7. Januar 2016 abgewiesen.
Mit Eingabe vom 15. Februar 2016 führen A.A._ und B.A._ Beschwerde in öffentlich-rechtlichen Angelegenheiten beim Bundesgericht und beantragen im Wesentlichen, auf den Widerruf der Niederlassungsbewilligung von A.A._ sei zu verzichten und die Aufenthaltsbewilligung von B.A._ sei zu verlängern. Während die Sicherheitsdirektion und das Verwaltungsgericht des Kantons Zürich auf eine Vernehmlassung verzichten, schliesst das Staatssekretariat für Migration (SEM) auf Abweisung der Beschwerde. Mit Schreiben vom 12. Mai 2016 hat das Bundesgericht den Betroffenen das Vernehmlassungsergebnis mitgeteilt; innert der hierfür angesetzten Frist erfolgte keine (fakultative) Eingabe von A.A._ und B.A._.
2.
Die Beschwerde erweist sich als offensichtlich unbegründet, weswegen sie im vereinfachten Verfahren gemäss Art. 109 Abs. 2 lit. a i.V.m. Abs. 3 BGG, d.h. mit summarischer Begründung und unter Verweis auf den angefochtenen Entscheid zu erledigen ist:
2.1. Gemäss Art. 63 Abs. 2 in Verbindung mit Art. 62 lit. b AuG kann die Niederlassungsbewilligung einer ausländischen Person, welche sich seit mehr als fünfzehn Jahren ordnungsgemäss und ununterbrochen in der Schweiz aufhält, widerrufen werden, wenn diese zu einer längerfristigen Freiheitsstrafe verurteilt wurde. Als "längerfristig" gilt jede Freiheitsstrafe, deren Dauer ein Jahr überschreitet (<ref-ruling> E. 4.2 und E. 4.5 S. 379 ff.). Dieses Erfordernis ist hier in Bezug auf den Beschwerdeführer 1 offensichtlich erfüllt. Er beruft sich im Wesentlichen einzig darauf, dass der angeordnete Bewilligungswiderruf unverhältnismässig sei. Diese Rüge geht jedoch ins Leere: Richtig ist wohl, dass ein Widerruf der Niederlassungsbewilligung aufgrund der gesamten Umstände des Einzelfalls verhältnismässig sein muss (<ref-ruling> E. 4.3 S. 381 f. m.w.H). Dies hat das Verwaltungsgericht aber nicht verkannt, sondern es hat die hier massgebenden öffentlichen Interessen an einer Ausreise des Beschwerdeführers 1 und dessen private Interessen an einem Verbleib in der Schweiz umfassend und sachgerecht gewürdigt und es für zumutbar erachtet, dass der Beschwerdeführer 1 in seine Heimat zurückkehrt.
2.2. Diese Schlussfolgerung der Vorinstanz ist weder im Lichte des Ausländergesetzes noch unter dem Blickwinkel der EMRK zu beanstanden: Wie das Verwaltungsgericht zutreffend ausgeführt hat, ist der Ausgangspunkt und Massstab für die Schwere des Verschuldens und die fremdenpolizeiliche Interessenabwägung die vom Strafrichter verhängte Strafe (Urteil 2C_295/2009 vom 25. September 2009 E. 5.3, nicht publ. in <ref-ruling>; <ref-ruling> E. 3.1 S. 216). Insgesamt musste der Beschwerdeführer 1 innert sieben Jahren achtmal strafrechtlich verurteilt werden, woraus Freiheitsstrafen von insgesamt knapp drei Jahren resultierten. Dies deutet auf ein erhebliches Verschulden hin und lässt auf eine ausgeprägte Geringschätzung und Gleichgültigkeit gegenüber der schweizerischen Rechtsordnung schliessen. Dieser Eindruck wird durch die Tatsache verstärkt, dass sich der Beschwerdeführer 1 weder von diversen Strafen mit warnendem Charakter (Bussen/Geldstrafen, bedingte Freiheitsstrafen) noch von hängigen Strafverfahren oder von zwei ausdrücklichen fremdenpolizeilichen Verwarnungen samt Androhung des Bewilligungswiderrufs beeindrucken liess. Bei dieser Sachlage ist in ausländerrechtlicher Hinsicht trotz den gegenteiligen Vorbringen des Beschwerdeführers 1 weiterhin von einem erheblichen Rückfallrisiko auszugehen, zumal die von ihm verübten Straftaten noch nicht besonders lange zurückliegen. Seit dem 12. Oktober 2015 befindet er sich zudem im Strafvollzug, so dass die seit der letzten Delinquenz verstrichene Zeit noch zusätzlich zu relativieren ist. Der weitere Verbleib des Beschwerdeführers 1 im Land ist somit mit den Sicherheitsinteressen der Schweiz nicht zu vereinbaren. Was schliesslich die von den Beschwerdeführern ebenfalls angerufene Kinderrechtskonvention angeht, so hat das Bundesgericht bereits mehrfach festgehalten, dass sich daraus kein unmittelbarer Anspruch auf die Erteilung einer ausländerrechtlichen Bewilligung ergibt (<ref-ruling> E. 2.4 S. 321; <ref-ruling> E. 5 S. 391 f.; <ref-ruling> E. 3b S. 367). Im Übrigen hat das Verwaltungsgericht auch die Situation der Tochter in die Interessenabwägung miteinbezogen und nachvollziehbar festgestellt, dass sich das anderthalbjährige Kind noch in einem anpassungsfähigen Alter befindet.
2.3. Da sich der Widerruf der Niederlassungsbewilligung des Beschwerdeführers 1 somit als rechtens erweist und der Beschwerdeführer 1 daher über kein Anwesenheitsrecht in der Schweiz mehr verfügt, ergibt sich ohne Weiteres, dass auch die Nichtverlängerung der Aufenthaltsbewilligung der Beschwerdeführerin 2 zu Recht erfolgte, zumal der Bewilligungsanspruch der Ehegattin an das Bestehen der Niederlassungsbewilligung des Ehegatten anknüpft (Art. 43 Abs. 1 AuG). Im Übrigen reiste die Beschwerdeführerin 2 erst vor rund zwei Jahren in die Schweiz ein, als der Beschwerdeführer 1 bereits achtmal strafrechtlich verurteilt war und er aufgrund des neuesten Straferkenntnisses mit einem Widerruf seines Aufenthaltstitels rechnen musste, weswegen die Gatten nicht in guten Treuen davon ausgehen durften, ihr Familienleben in der Schweiz führen zu können.
3.
Nach dem Ausgeführten ist die Beschwerde abzuweisen.
Entsprechend diesem Verfahrensausgang haben die Beschwerdeführer die bundesgerichtlichen Kosten unter solidarischer Haftbarkeit zu tragen (<ref-law>).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird abgewiesen.
2.
Die Gerichtskosten von Fr. 2'000.-- werden den Beschwerdeführern unter solidarischer Haftbarkeit auferlegt.
3.
Dieses Urteil wird den Verfahrensbeteiligten, dem Verwaltungsgericht des Kantons Zürich, 4. Abteilung, sowie dem Staatssekretariat für Migration schriftlich mitgeteilt.
Lausanne, 30. Juni 2016
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Seiler
Der Gerichtsschreiber: Zähndler