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. 