Sachverhalt: A. A._ und B._ sind kosovarische Staatsangehörige und wohnen in Frankreich. Die Staatsanwaltschaft Muri-Bremgarten wirft ihnen vor, am 26. März 2015 ohne Bewilligung zur Aufnahme einer Erwerbsarbeit in die Schweiz eingereist zu sein, sich hier aufgehalten und auf der Baustelle von C._ in Zufikon gearbeitet zu haben. Mit Strafbefehlen vom 3. Juni 2015 sprach die Staatsanwaltschaft die beiden der mehrfachen Widerhandlung gegen das Ausländergesetz (rechtswidrige Einreise, rechtswidriger Aufenthalt und Arbeitsaufnahme ohne Bewilligung) für schuldig und auferlegte ihnen eine bedingte Geldstrafe von 120 Tagessätzen zu Fr. 30.-- bei einer Probezeit von zwei Jahren, sowie eine Busse von Fr. 900.--. A._ und B._ erhoben gegen die beiden Strafbefehle Einsprache. Am 24. September 2015 beantragten sie eine amtliche Verteidigung. Mit zwei separaten Verfügungen vom 21. Oktober 2015 wies die Staatsanwaltschaft die beiden Gesuche ab. Dagegen erhoben A._ und B._ Beschwerde ans Obergericht des Kantons Aargau. Mit Entscheid vom 24. November 2015 vereinigte dieses die beiden Verfahren und wies die Beschwerden ab. Die Gesuche um Gewährung der unentgeltlichen Rechtspflege für das Beschwerdeverfahren wies es ebenfalls ab, da ihm die Beschwerden als offensichtlich aussichtslos erschienen. B. Mit Beschwerde in Strafsachen ans Bundesgericht vom 18. Januar 2016 beantragen A._ und B._, der Entscheid des Obergerichts sei aufzuheben und Rechtsanwalt Franz Hollinger sei zum amtlichen Verteidiger zu bestellen. Zudem sei der Kanton Aargau zu verpflichten, die Beschwerdeführer für das kantonale und das bundesgerichtliche Verfahren mit insgesamt Fr. 3'000.-- zu entschädigen. Eventuell sei den Beschwerdeführern für das kantonale Verfahren die unentgeltliche Rechtspflege zu gewähren, Rechtsanwalt Franz Hollinger als unentgeltlicher Rechtsbeistand einzusetzen und die Vorinstanz anzuweisen, dessen Honorar festzulegen. Die Staatsanwaltschaft und das Obergericht haben auf eine Vernehmlassung verzichtet.