Sachverhalt: A. Die Y._ AG (Beschwerdegegnerin) erbringt Dienstleistungen für die Schweizerischen Bundesbahnen (SBB). Anfangs 2006 plante sie eine Zusammenarbeit mit der Z._ Park AG. Gegenstand dieser Zusammenarbeit, die unter dem Titel "Y._--Schwerpunkt 2006" lief, war ein Kombi-Angebot, mit dem man zu vergünstigten Tarifen mit den SBB nach K._ reisen und den Z._ Park besichtigen konnte. Die Beschwerdegegnerin sollte gegen ein Entgelt seitens der Z._ Park AG unter anderem die schweizweite Vermarktung des Angebots übernehmen. Da sich die Z._ Park AG zum genannten Zeitpunkt in wirtschaftlichen Schwierigkeiten befand, kam für die Beschwerdegegnerin eine Zusammenarbeit nur gegen eine finanzielle Sicherheit in Frage. Am 9. März 2006 gab die X._ AG (Beschwerdeführerin), deren Verwaltungsratsdelegierter A._ damals auch Verwaltungsratspräsident ad interim der Z._ Park AG war, gegenüber der Beschwerdegegnerin folgende schriftliche Erklärung ab: " Partneranteil Z.Y._-Schwerpunkt 2006 (...) Die X._ A garantiert unwiderruflich den Partneranteil des Z._ Parks am Y._-Schwerpunkt 2006 von CHF 50'000.00. Berechnung des Ausfalles: Sollte der Z._ Park in den Konkurs oder in den Nachlass gehen müssen, entschädigt X._ AG die Y._ AG, den Betrag zwischen der Konkurs- resp. Nachlassdividende und dem garantierten Betrag von CHF 50'000.00, d.h. bis zum maximalen Betrag von CHF 50'000.00. (...) " Am 15. April 2006 stellte die Beschwerdegegnerin der Z._ Park AG für Werbe-, Kommunikations- und Distributionskosten der Y._-Broschüre Freizeitparks einen Pauschalbetrag von Fr. 50'000.-- zuzüglich 7.6% MwSt, total Fr. 53'800.--, in Rechnung. Die Z._ Park AG bezahlte die Rechnung nicht. Am 10. Juli 2006 wurde der Z._ Park AG Nachlassstundung für sechs Monate gewährt. Am 21. Juli 2006 meldete die Beschwerdegegnerin bei der Sachwalterin einen Forderungsbetrag von insgesamt Fr. 75'592.45 an. Darin enthalten war die Forderung über Fr. 53'800.--. Die angemeldete Forderung wurde (weitestgehend) anerkannt und zugelassen. Am 30. Oktober 2009 orientierte die Sachwalterin die Beschwerdegegnerin, dass sie eine Nachlassdividende von Fr. 9'602.35 ausbezahlt erhalte. Am 31. Dezember 2009 und - nach Nichtbezahlung - erneut am 5. November 2010 stellte die Beschwerdegegnerin der Beschwerdeführerin unter Bezugnahme auf deren Erklärung vom 9. März 2006 den Betrag von Fr. 40'397.65 in Rechnung (Fr. 50'000.-- abzüglich der erhaltenen Nachlassdividende von Fr 9'602.35). Die Beschwerdeführerin beglich die Rechnung nicht. B. Nach erfolglosem Sühneverfahren erhob die Beschwerdegegnerin am 19. Januar 2011 beim Bezirksgericht Prättigau/Davos Klage gegen die Beschwerdeführerin und begehrte deren Verpflichtung zur Zahlung von Fr. 40'397.65 nebst Zins zu 5% seit 8. November 2010, wobei sie für Fr. 3'208.80 einen Nachklagevorbehalt anbrachte. Mit Urteil vom 1. März 2012 hiess das Bezirksgericht die Klage teilweise gut und verpflichtete die Beschwerdeführerin, der Beschwerdegegnerin Fr. 40'397.65 nebst Zins zu 5% seit dem 8. November 2010 zu bezahlen. Gegen dieses Urteil erhob die Beschwerdeführerin Berufung an das Kantonsgericht von Graubünden und verlangte, die Klage sei vollumfänglich abzuweisen, da die Beschwerdegegnerin die Hauptschuld nicht nachgewiesen habe. Eventualiter sei die Beschwerdegegnerin zu verpflichten, " die Hauptschuld gesetzeskonform der Beklagten nachzuweisen, d.h. die Projekt-Buchhaltung des Projektes 'Y._ -Schwerpunkt 2006' (Einnahmen und Ausgaben - Datum Auftragserteilung und Kostenfolge der Drittrechnungen - sowie der berechnete Anteil Y._ und Z._ Park, ausgehend vom Datum der Bürgschaft, d.h. vom 9. März 2006) ". Die Beschwerdegegnerin trug auf Abweisung der Berufung an und erhob Anschlussberufung, mit der sie eine Parteientschädigung für das erstinstanzliche Verfahren von Fr. 16'731.75 (anstatt der zugesprochenen Fr. 13'961.30) verlangte. Mit Urteil vom 13. Februar 2013 wies das Kantonsgericht die Berufung ab und hiess die Anschlussberufung gut. C. Die Beschwerdeführerin beantragt mit Beschwerde in Zivilsachen, das Urteil des Kantonsgerichts vollumfänglich aufzuheben und Herrn B._ als Zeugen die Frage zu stellen, "ob er die Power-Point-Präsentation ohne Datum und Referenzierung" gesehen habe. Es sei der Beschwerdeführerin "somit" das rechtliche Gehör zu gewähren. Eventualiter sei die Beschwerdegegnerin zu verpflichten, "die Hauptschuld gesetzeskonform der Beklagten nachzuweisen, d.h. die Projekt-Buchhaltung des Projektes ' Y._-Schwerpunkt 2006' (Einnahmen und Ausgaben - Datum Auftragserteilung und Kostenfolge der Drittrechnungen - sowie der berechnete Anteil Y._ und Z._ Park, ausgehend vom Datum der Bürgschaft, d.h. vom 9. März 2006) ". Die Beschwerdegegnerin und die Vorinstanz beantragen, die Beschwerde abzuweisen, soweit darauf einzutreten sei. Mit Präsidialverfügung vom 8. Mai 2013 wurde das Gesuch der Beschwerdegegnerin um Sicherstellung der Parteientschädigung abgewiesen.