Sachverhalt:
A. Die Y._ (Beschwerdegegnerin) nahm für die X._ AG (Beschwerdeführerin) jeweils die Einfuhrverzollung an der Zollstelle in Schaanwald vor.
Die Beschwerdeführerin importierte im Mai 2007 eine Ladung Geflügelprodukte mit einem Nettogewicht von 16'076 kg aus Slowenien in die Schweiz. Über die Art der Waren, das Brutto-/Nettogewicht sowie das Taxgewicht informierte sie die Beschwerdegegnerin am 12. Mai 2007 vorab per Telefax. Der Lastwagen traf am 14. Mai 2007 abends an der Zollstelle Schaanwald ein. In der Folge gelang es der Beschwerdegegnerin nicht, die gesamte Ware zum Kontingentzollansatz zu verzollen, da die Beschwerdeführerin gemäss Systemangaben zu jenem Zeitpunkt nicht über genügend Kontingente verfügte. Am 15. Mai 2007 führten A._ von der Beschwerdegegnerin und der für die Beschwerdeführerin handelnde B._ ein Telefongespräch, dessen Inhalt umstritten ist. Die Beschwerdegegnerin verzollte daraufhin einen Teil der Ware zum Ausserkontingentzollansatz, bezahlte die entsprechende Rechnung der Eidgenössischen Oberzolldirektion über Fr. 97'284.55 und stellte diesen Betrag - zuzüglich ihrer Provision von Fr. 501.10 - der Beschwerdeführerin in Rechnung. Die Beschwerdeführerin stellte sich in der Folge auf den Standpunkt, nie mit einer Verzollung zum Ausserkontingentzollansatz einverstanden gewesen zu sein und verweigerte die Zahlung.
B. Am 30. Juli 2008 klagte die Beschwerdegegnerin beim Handelsgericht des Kantons Zürich gegen die Beschwerdeführerin auf Zahlung von Fr. 97'785.65 nebst Zins zu 5 % seit dem 20. Mai 2007. Gleichzeitig beantragte die Beschwerdegegnerin, es sei ihr in der über diesen Betrag eingeleitete Betreibung die definitive Rechtsöffnung zu erteilen. Ausserdem sei die Beschwerdeführerin zur Zahlung vorprozessualer Anwaltskosten im Betrag von Fr. 3'166.05 zuzüglich Zins zu 5 % ab dem 5. Mai 2008 zu verurteilen.
Am 29. Januar 2009 fand die Referentenaudienz mit Vergleichsverhandlung statt, die jedoch nicht zu einer Einigung führte. In der Folge wurde das Verfahren schriftlich fortgesetzt. Am 10. November 2010 fand vor dem Gesamtgericht die Beweisverhandlung statt, an welcher A._ und B._ als Zeugen befragt wurden.
Mit Urteil vom 13. Januar 2011 verpflichtete das Handelsgericht des Kantons Zürich die Beschwerdeführerin, der Beschwerdegegnerin Fr. 97'785.65 nebst 5 % Zins seit dem 8. April 2008 zu bezahlen. Den Rechtsvorschlag in der eingeleiteten Betreibung hob es im gleichen Umfang auf. Im Mehrbetrag wies das Handelsgericht die Klage ab. Die Gerichtsgebühr setzte es auf Fr. 18'000.-- fest, wobei es die Kosten zu 3 % der Beschwerdegegnerin und zu 97 % der Beschwerdeführerin auferlegte. Letztere wurde zudem verpflichtet, der Beschwerdegegnerin eine Prozessentschädigung von Fr. 21'000.-- (inkl. Weisungskosten) zu bezahlen.
Das Handelsgericht sah es aufgrund der Zeugenaussagen als erwiesen an, dass die Beschwerdegegnerin von der Beschwerdeführerin angewiesen worden sei, die Verzollung vorläufig zum Ausserkontingentzollansatz vorzunehmen und später eine Umbuchung beantragt werde. Die geplante Umbuchung sei in der Folge jedoch ausgeblieben. Die Beschwerdegegnerin habe die Verzollung weisungsgemäss vorgenommen, weshalb sie als Auftragnehmerin Anspruch sowohl auf das Honorar wie auch auf den Auslagenersatz habe. In Bezug auf die von der Beschwerdegegnerin eingeklagten vorprozessualen Rechtsverfolgungskosten erwog das Handelsgericht, diese Aufwendungen seien im Rahmen der Prozessentschädigung zuzusprechen, weshalb die Klage diesbezüglich abzuweisen sei.
C. Mit Beschwerde in Zivilsachen beantragt die Beschwerdeführerin dem Bundesgericht, es sei die Klage der Beschwerdegegnerin in Gutheissung der Beschwerde abzuweisen.
Die Beschwerdegegnerin beantragt die Abweisung der Beschwerde. Die Vorinstanz verweist hinsichtlich der durchgeführten Referentenaudienz auf eine Stellungnahme des verantwortlichen Instruktionsrichters und verzichtet im Übrigen auf eine Vernehmlassung.
D. Mit Verfügung vom 13. Mai 2011 wies das Bundesgericht das Gesuch der Beschwerdeführerin um Ansetzung einer Frist zur Einreichung einer Replik ab und wies die Beschwerdeführerin darauf hin, dass Verzicht auf Stellungnahme angenommen werde, sofern die Replikschrift nicht bis 31. Mai 2011 beim Bundesgericht eingehe.
Mit Eingabe vom 19. Mai 2011 verzichtete die Beschwerdeführerin auf eine ausführliche Replikschrift und reichte dem Bundesgericht eine vom 13. Mai 2011 datierende Erklärung ihres Rechtsvertreters sowie von C._ hinsichtlich des Ablaufs der Referentenaudienz vom 29. Januar 2009 ein. Mit Eingabe vom 31. Mai 2011 äusserte sich die Beschwerdegegnerin zur Replik.

Erwägungen:
1. 1.1 Das Bundesgericht wendet das Recht von Amtes wegen an (<ref-law>). Es ist somit weder an die in der Beschwerde geltend gemachten Argumente noch an die Erwägungen der Vorinstanz gebunden; es kann eine Beschwerde aus einem anderen als dem angerufenen Grund gutheissen und es kann eine Beschwerde mit einer von der Argumentation der Vorinstanz abweichenden Begründung abweisen (vgl. <ref-ruling> E. 1.4.1 S. 254; <ref-ruling> E. 2.5 S. 262; <ref-ruling> E. 1.4 S. 140). Immerhin prüft das Bundesgericht, unter Berücksichtigung der allgemeinen Begründungspflicht der Beschwerde (Art. 42 Abs. 1 und 2 BGG), grundsätzlich nur die geltend gemachten Rügen, sofern die rechtlichen Mängel nicht geradezu offensichtlich sind. Es ist jedenfalls nicht gehalten, wie eine erstinstanzliche Behörde alle sich stellenden rechtlichen Fragen zu untersuchen, wenn diese vor Bundesgericht nicht mehr vorgetragen werden (<ref-ruling> E. 2.2.1 S. 389; <ref-ruling> E. 1.4.1 S. 254 mit Hinweisen). Eine qualifizierte Rügepflicht gilt hinsichtlich der Verletzung von Grundrechten und von kantonalem und interkantonalem Recht. Das Bundesgericht prüft eine solche Rüge nur insofern, als sie in der Beschwerde präzise vorgebracht und begründet worden ist (<ref-law>). Macht der Beschwerdeführer beispielsweise eine Verletzung des Willkürverbots (<ref-law>) geltend, genügt es nicht, wenn er einfach behauptet, der angefochtene Entscheid sei willkürlich; er hat vielmehr im Einzelnen zu zeigen, inwiefern der angefochtene Entscheid offensichtlich unhaltbar ist (<ref-ruling> E. 3 S. 352; <ref-ruling> E. 5.5 S. 5; <ref-ruling> E. 3.2 S. 444).
Willkür im Sinne von <ref-law> liegt nach ständiger Rechtsprechung nicht schon dann vor, wenn eine andere Lösung ebenfalls vertretbar erscheint oder gar vorzuziehen wäre. Das Bundesgericht hebt einen kantonalen Entscheid wegen Willkür nur auf, wenn er offensichtlich unhaltbar ist, zur tatsächlichen Situation in klarem Widerspruch steht, eine Norm oder einen unumstrittenen Rechtsgrundsatz krass verletzt oder in stossender Weise dem Gerechtigkeitsgrundsatz zuwiderläuft. Willkür liegt zudem nur vor, wenn nicht bloss die Begründung eines Entscheids, sondern auch das Ergebnis unhaltbar ist (<ref-ruling> E. 1.3 S. 4 f.; <ref-ruling> E. 4.1 S. 133; <ref-ruling> E. 2.1 S. 211; je mit Hinweisen).
1.2 Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat (<ref-law>). Es kann die Sachverhaltsfeststellung der Vorinstanz nur berichtigen oder ergänzen, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht (<ref-law>). Überdies muss die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein (<ref-law>). Neue Tatsachen und Beweismittel dürfen nur soweit vorgebracht werden, als der Entscheid der Vorinstanz dazu Anlass gibt (<ref-law>).
Der Beschwerdeführer, der die Sachverhaltsfeststellungen der Vorinstanz anfechten will, muss substantiiert darlegen, inwiefern die Voraussetzungen einer Ausnahme gemäss <ref-law> gegeben sind und das Verfahren bei rechtskonformer Ermittlung des Sachverhalts anders ausgegangen wäre; andernfalls kann ein Sachverhalt, der vom im angefochtenen Entscheid festgestellten abweicht, nicht berücksichtigt werden. Auf eine Kritik an den tatsächlichen Feststellungen der Vorinstanz, die diesen Anforderungen nicht genügt, ist nicht einzutreten (vgl. <ref-ruling> E. 1.3 S. 351 f., 393 E. 7.1 S. 398, 462 E. 2.4 S. 466 f.). Insbesondere genügt es nicht, dem Bundesgericht unter gelegentlichem Hinweis auf die Akten einfach einen über die tatsächlichen Feststellungen im angefochtenen Entscheid hinausgehenden Sachverhalt zu unterbreiten, daraus vom angefochtenen Urteil abweichende Schlüsse zu ziehen und dieses als willkürlich zu bezeichnen. Ein derartiges Vorgehen verkennt die grundsätzliche Bindung des Bundesgerichts an die tatsächlichen Feststellungen im angefochtenen Entscheid (Art. 97 und Art. 105 BGG). Es geht nicht an, in einer Beschwerde in Zivilsachen appellatorische Kritik an der Beweiswürdigung des kantonalen Gerichts zu üben und Ergänzungen bezüglich der tatsächlichen Feststellungen vorzunehmen, als ob dem Bundesgericht im Beschwerdeverfahren die freie Überprüfung aller Tatfragen zukäme. Das Bundesgericht ist keine letzte Appellationsinstanz, die den angefochtenen Entscheid in tatsächlicher Hinsicht frei überprüfen könnte.
1.3 Diese Grundsätze verkennt die Beschwerdeführerin in verschiedener Hinsicht.
1.3.1 Sie behauptet im Zusammenhang mit dem Ablauf der Referentenaudienz, es dränge sich der Verdacht auf, dass wesentliche Behauptungen und Darlegungen in der Replik der Beschwerdegegnerin in Abwesenheit der Beschwerdeführerin anlässlich der Vergleichsgespräche von den beteiligten Richtern "in die Feder diktiert" worden seien. Die Beschwerdeführerin legt weder dar, auf welche konkreten in der Replik aufgestellten Behauptungen sie sich bezieht, geschweige denn zeigt sie mit Aktenhinweisen auf, entsprechende Behauptungen bereits im vorinstanzlichen Verfahren aufgestellt zu haben. Ihre Vorbringen haben damit unbeachtet zu bleiben (vgl. <ref-law>).
1.3.2 Neu und damit unbeachtlich (<ref-law>) ist die mit Replik vom 19. Mai 2011 erstmals im bundesgerichtlichen Beschwerdeverfahren eingereichte Erklärung des Rechtsvertreters der Beschwerdeführerin und von C._ hinsichtlich des Ablaufs der Referentenaudienz vom 29. Januar 2009.
1.3.3 Rein appellatorisch sind die Ausführungen der Beschwerdeführerin zur vorinstanzlichen Einschätzung der Glaubwürdigkeit der Zeugen A._ und B._. Sie unterbreitet dem Bundesgericht lediglich verschiedene Indizien, die ihrer Ansicht nach gegen die Glaubwürdigkeit des Zeugen A._ und für diejenige des Zeugen B._ sprechen und zweifelt damit die vorinstanzlichen Feststellungen an. Darauf ist nicht einzutreten.
Ebenso appellatorisch ist das unter Hinweis auf das Aussageprotokoll erhobene Vorbringen, der Zeuge A._ habe ausgesagt, dass eine nachträgliche Verzollung seines Wissens immer möglich sei, während der Zeuge B._ davon keine Kenntnis gehabt habe, was "stark dagegen" spreche, dass der Zeuge B._ die Weisung erteilt habe, die Verzollung vorzunehmen; vielmehr spreche es "stark dafür", dass die Beschwerdeführerin eigenmächtig verzollt habe. Ebenso unbeachtlich ist der im gleichen Zusammenhang erhobene Einwand, niemand sei "nach allgemeiner Lebenserfahrung bereit, gratis ein Delcredere-Risiko von über Fr. 95'000.-- einzugehen ohne irgendeine Sicherheit und ohne irgendein Honorar". Damit erhebt sie keine gehörige Sachverhaltsrüge. Ihre gleichzeitig erhobene, jedoch nicht weiter begründete Behauptung, die Vorinstanz sei ihrer Begründungspflicht nicht nachgekommen und habe damit Art. 6 EMRK und <ref-law> verletzt, verfehlt die gesetzlichen Anforderungen an eine hinreichend begründete Verfassungsrüge (<ref-law>).
1.3.4 Hinsichtlich des Zeit- und Handlungsdrucks, die Verzollung der gekühlten Ladung vorzunehmen, behauptet die Beschwerdeführerin entgegen den vorinstanzlichen Feststellungen, die zertifizierten Kühlfahrzeuge, die für derartige Transporte verwendet würden, seien für entsprechende Situationen ausgerüstet und könnten mehrere Tage ohne Weiteres am Zoll stehen, um die unverderbliche Lieferung der Ware zu garantieren. Mit der blossen Behauptung, weder die Vorinstanz noch die Beschwerdegegnerin hätten jemals bestritten, dass das fragliche Fahrzeug über die notwendigen Kühlfähigkeiten über längere Zeit verfügt habe, erhebt die Beschwerdeführerin keine hinreichend begründete Sachverhaltsrüge.
Ebenso wenig erhebt sie eine rechtsgenügende Sachverhaltsrüge, wenn sie entgegen den Feststellungen im angefochtenen Entscheid, wonach der Lastwagenfahrer nur auf Veranlassung der Beschwerdeführerin erneut zur Zollstelle gefahren sei, behauptet, es sei der Zeuge A._ gewesen, der mit dem Chauffeur kommuniziert hätte, zumal die Verzollung anders gar nicht hätte vorgenommen werden können.
Hinsichtlich der Feststellung der Vorinstanz, dass gemäss dem Zeugen B._ nur ein Telefonat, nach der Aussage der Beschwerdeführerin jedoch deren zwei stattgefunden hätten, bringt die Beschwerdeführerin lediglich vor, nach so langer Zeit sei es offensichtlich, dass ein Zeuge sich nicht mehr an ein einzelnes Telefonat erinnert könne, sie zeigt jedoch nicht auf, inwiefern der angefochtene Entscheid im Ergebnis willkürlich sein soll.
2. Die Beschwerdeführerin bringt vor Bundesgericht vor, es seien mit der getrennten Führung der Vergleichsgespräche Art. 6 EMRK sowie <ref-law> verletzt worden. Es sei anzunehmen, dass die Beschwerdegegnerin sich gegenüber dem Gericht geäussert habe, wobei ihr eine entsprechende Vernehmlassung hierzu verunmöglicht worden sei.
Abgesehen davon, dass sich die Beschwerdeführerin mit ihren Ausführungen teilweise ohne weitere Begründung über den im angefochtenen Entscheid festgehaltenen Sachverhalt hinwegsetzt (siehe vorn E. 1.3.1), legt sie nicht konkret dar, inwiefern ihr durch den Ablauf der Vergleichsverhandlungen im Rahmen des inoffiziellen Teils der Referentenaudienz (§ 118 in Verbindung mit <ref-law> ZH), die ohne Protokollierung vor sich gehen, in denen Äusserungen der Parteien, Anwälte und Gerichtspersonen als unpräjudiziell gelten und die inhaltlich nicht auf den eingeklagten Streitgegenstand beschränkt sind (vgl. etwa HANS NIGG, Der Weg zum gerichtlichen Vergleich, in: Walter Fellmann/Stephan Weber [Hrsg.], Haftpflichtprozess 2007, 2007, S. 104 f.), eine Stellungnahme zu den Vorbringen der Beschwerdegegnerin im Verfahren verunmöglicht worden wäre. Ebenso wenig zeigt sie mit Aktenhinweisen auf, dass sie mit dem Ablauf der - von der Mitwirkung der Parteien abhängigen - Vergleichsgespräche nicht einverstanden gewesen wäre.
Eine Verletzung von Art. 6 EMRK bzw. <ref-law> wird mit den Ausführungen der Beschwerdeführerin nicht hinreichend dargetan.
3. Die Beschwerdeführerin wirft der Vorinstanz eine Verletzung von <ref-law> vor.
3.1 Die Vorinstanz führte aus, die Beschwerdegegnerin habe, nachdem die Verzollung zum Ausserkontingentansatz vorgenommen worden sei, beim Eidgenössischen Finanzdepartement ein Gesuch um nachträgliche Zulassung zum Kontingentzollansatz gestellt. Die Eidgenössische Zollverwaltung habe der Beschwerdegegnerin mit Schreiben vom 9. November 2007 mitgeteilt, dass eine Änderung der Verzollung nicht mehr möglich sei. Die Vorinstanz erwog, es müsse nicht abschliessend überprüft werden, weshalb eine nachträgliche Zulassung der Geflügelpartie zum Kontingentzollansatz nicht mehr möglich gewesen sei. Die Beschwerdegegnerin führe zwar aus, so die Vorinstanz weiter, sie habe den Auftrag erhalten, den Antrag an die Eidgenössische Zollverwaltung auf Umschreibung der Ware auf den Kontingentzollansatz zu stellen, indessen mache sie daraus keine Ansprüche geltend. Die Beschwerdeführerin ihrerseits sei der Ansicht, dass das Beschwerdeverfahren wegen der mangelnden Kompetenz der Beschwerdegegnerin nicht habe erfolgreich abgeschlossen werden können. Da auch sie weder im Sinne einer Verrechnungseinrede noch im Sinne einer Widerklage konkrete Ansprüche stelle, könne diesbezüglich eine Überprüfung unterbleiben.
3.2 Die Beschwerdeführerin bringt zu Recht vor, die Erhebung einer Verrechnungseinrede oder einer Widerklage sei gar nicht notwendig gewesen. Der Auftrag (<ref-law>) an den Beauftragten umfasst nur die Zustimmung zu notwendigen Aufwendungen. Unberechtigte Auslagen und Verwendungen sind durch den Mandatskonsens nicht gedeckt, weshalb der Auftraggeber den Ersatz unnötiger oder überhöhter Auslagen ablehnen darf. Bezüglich solcher Auslagen liegt nicht eine Schlechterfüllung des Beauftragten vor, die Schadenersatzansprüche begründen könnte; vielmehr sind die Aufwendungen des Beauftragten als Nichtleistung zu qualifizieren, für die kein Ersatz geschuldet ist (WALTER FELLMANN, Berner Kommentar, 1992, N. 77 zu <ref-law>; FRANZ WERRO, in: Commentaire romand, Code des obligations I, 2003, N. 7 zu <ref-law>; vgl. auch Urteil 4C.199/2004 vom 11. Januar 2005 E. 10.3.2.1).
Entsprechend musste die Beschwerdeführerin, die dem von der Beschwerdegegnerin eingeklagten Anspruch auf Verwendungsersatz (<ref-law>) entgegenhielt, eine Umbuchung sei möglich gewesen, jedoch aus Gründen gescheitert, die von der Beschwerdegegnerin zu vertreten seien, keine Verrechnungseinrede oder eine Widerklage erheben. Vielmehr genügte ihre Einwendung, die Beschwerdegegnerin habe die getätigten Auslagen aufgrund ihres unsorgfältigen Vorgehens selbst zu tragen, indem sie trotz Aufforderung der Eidgenössischen Zollverwaltung nie Anstalten unternommen habe, die erforderlichen Belege einzureichen.
Nach den Feststellungen im angefochtenen Entscheid war hinsichtlich der Zollgebühren eine Vorauszahlungspflicht der Beschwerdegegnerin vereinbart. Beide Parteien gingen von der grundsätzlichen Möglichkeit der nachträglichen Umbuchung aus und brachten im vorinstanzlichen Verfahren übereinstimmend vor, dass die Beschwerdegegnerin gemäss Absprache mit der Beschwerdeführerin bei der Eidgenössischen Zollverwaltung eine Korrektur der erfolgten Veranlagung zu erwirken suche. Schuldete die Beschwerdegegnerin gar keinen Zoll, weil die Veranlagung nach dem Ausserkontingentzollansatz nachträglich geändert werden konnte, erlangte sie für solche unnötigen Kosten auch keinen Anspruch auf Auslagenersatz nach <ref-law>. Die Vorinstanz hat es daher zu Unrecht unterlassen zu prüfen, ob die Verweigerung der nachträglichen Zulassung zum Kontingentzollansatz durch die Zollbehörden - wie von der Beschwerdeführerin behauptet - auf eine Nachlässigkeit der Beschwerdegegnerin zurückzuführen war und konnte es nicht bei der blossen Vermutung bewenden lassen, dass die Umschreibung nicht mehr möglich gewesen sei, weil von der Beschwerdeführerin nicht für die ganze Ladung Kontingente übertragen worden waren.
4. Die Beschwerdeführerin rügt hinsichtlich der Festsetzung der Parteientschädigung eine Missachtung der Begründungspflicht nach <ref-law> sowie Art. 6 EMRK.
4.1 Die Vorinstanz hielt zu dem von der Beschwerdegegnerin eingeklagten Ersatz vorprozessualer Anwaltskosten fest, vorprozessuale Rechtsverfolgungskosten seien nach der zürcherischen Praxis nicht als Schadensposten geltend zu machen, sondern bei der Bemessung der Prozessentschädigung nach Massgabe des beidseitigen Unterliegens bzw. Obsiegens zu berücksichtigen. Somit seien die von der Beschwerdegegnerin geltend gemachten Aufwendungen ihres Rechtsvertreters im Rahmen der Prozessentschädigung zuzusprechen, weshalb die Klage diesbezüglich abzuweisen sei.
4.1 Die Vorinstanz hielt zu dem von der Beschwerdegegnerin eingeklagten Ersatz vorprozessualer Anwaltskosten fest, vorprozessuale Rechtsverfolgungskosten seien nach der zürcherischen Praxis nicht als Schadensposten geltend zu machen, sondern bei der Bemessung der Prozessentschädigung nach Massgabe des beidseitigen Unterliegens bzw. Obsiegens zu berücksichtigen. Somit seien die von der Beschwerdegegnerin geltend gemachten Aufwendungen ihres Rechtsvertreters im Rahmen der Prozessentschädigung zuzusprechen, weshalb die Klage diesbezüglich abzuweisen sei.
4.2 4.2.1 Der Anspruch auf rechtliches Gehör (<ref-law>) verlangt insbesondere, dass die Gerichte die rechtserheblichen Vorbringen der Parteien anhören und bei der Entscheidfindung berücksichtigen (<ref-ruling> E. 4.1 S. 88; <ref-ruling> E. 2 S. 242). Damit sich die Parteien ein Bild über die Erwägungen des Gerichts machen können, ist sein Entscheid zu begründen. Die Begründung muss kurz die Überlegungen nennen, von denen sich das Gericht hat leiten lassen und auf die sich sein Entscheid stützt (<ref-ruling> E. 2.4 S. 72). Nicht erforderlich ist hingegen, dass sich der Entscheid mit allen Parteistandpunkten einlässlich auseinandersetzt und jedes einzelne Vorbringen ausdrücklich widerlegt. Es genügt, wenn der Entscheid gegebenenfalls sachgerecht angefochten werden kann (<ref-ruling> E. 4.1 S. 88; <ref-ruling> E. 3.3 S. 445; <ref-ruling> E. 3.2 S. 236; je mit Hinweisen).
4.2.2 Die Beschwerdeführerin macht zu Recht geltend, dass sich aus der Begründung der Vorinstanz weder ergibt, welche konkret angefallenen - im vorinstanzlichen Verfahren bestrittenen - Kosten aufgrund welcher Beweismittel als ausgewiesen erachtet wurden, noch in welchem Umfang diese bei der Festsetzung der Parteientschädigung berücksichtigt wurden. Der Einwand der Beschwerdegegnerin, die Vorinstanz habe eben gerade keine vorprozessualen Aufwendungen zugesprochen, erscheint im Widerspruch zur vorinstanzlichen Erwägung, die Klage sei hinsichtlich der geltend gemachten Aufwendungen abzuweisen, weil sie im Rahmen der Prozessentschädigung zuzusprechen sei. Er zeigt jedoch immerhin, dass aufgrund der vorinstanzlichen Begründung nicht einmal restlos klar wird, ob die behaupteten Kosten mit der ohnehin geschuldeten, schematisch festgesetzten Parteientschädigung pauschal als abgegolten erachtet wurden oder ob sie zu einer erhöhten Parteientschädigung führten. Hinzu kommt, dass die Vorinstanz in der entsprechenden Erwägung ausführt, die Beschwerdegegnerin fordere in Ziffer 3 ihrer Rechtsbegehren Fr. 5'049.50 für ihre vorprozessualen Anwaltskosten (ein Betrag, der in einer Aufstellung der behaupteten Kosten in der Replik der Beschwerdegegnerin aufscheint), während gemäss den im angefochtenen Entscheid eingangs aufgeführten Rechtsbegehren unter diesem Titel lediglich ein Betrag von Fr. 3'166.05 eingeklagt wurde.
Die vorinstanzliche Begründung verunmöglichte es damit der Beschwerdeführerin, hinsichtlich der eingeklagten vorprozessualen Anwaltskosten bzw. der Festsetzung der Parteientschädigung die Tragweite des Entscheids zu erkennen und ihn in voller Kenntnis der Sache anzufechten. Die Rüge der Verletzung von <ref-law> ist begründet.
5. Das Urteil der Vorinstanz hält demnach einer Überprüfung teilweise nicht stand. Über den Antrag der Beschwerdeführerin auf Abweisung der Klage kann jedoch nicht entschieden werden, da die dafür erforderlichen tatsächlichen Feststellungen fehlen. Zudem fehlt es dem angefochtenen Entscheid hinsichtlich der geltend gemachten vorprozessualen Rechtsverfolgungskosten an einer hinreichenden Begründung. Entsprechend ist die Beschwerde in Zivilsachen teilweise gutzuheissen, das Urteil des Handelsgerichts des Kantons Zürich vom 13. Januar 2011 ist aufzuheben und die Sache gestützt auf <ref-law> zur Sachverhaltsergänzung und zu neuem Entscheid an die Vorinstanz zurückzuweisen.
Dem Ausgang des Verfahrens entsprechend wird die Beschwerdegegnerin kosten- und entschädigungspflichtig (Art. 66 Abs. 1 sowie Art. 68 Abs. 2 BGG).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird teilweise gutgeheissen, soweit darauf einzutreten ist, das Urteil des Handelsgerichts des Kantons Zürich vom 13. Januar 2011 wird aufgehoben und die Sache zu neuer Entscheidung an die Vorinstanz zurückgewiesen.
2. Die Gerichtskosten von Fr. 5'000.-- werden der Beschwerdegegnerin auferlegt.
3. Die Beschwerdegegnerin hat die Beschwerdeführerin für das bundesgerichtliche Verfahren mit Fr. 6'000.-- zu entschädigen.
4. Dieses Urteil wird den Parteien und dem Handelsgericht des Kantons Zürich schriftlich mitgeteilt.
Lausanne, 1. Juli 2011
Im Namen der I. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Klett
Der Gerichtsschreiber: Leemann