Sachverhalt: A. Im Sommer 1996 beabsichtigte die UBS (damals noch SBG), eine Wertsendung von DEM 1'500'000.-- von Zürich über Helsinki nach Tallin (Estland) an die Eesti Uhispank zu überweisen. Zu diesem Zweck schloss die UBS mit der Finnair (in Folgenden: die Beklagte) einen Frachtvertrag ab. Die Beklagte transportierte das Bargeld planmässig nach Tallin, wo es der Eesti Uhispank indessen nicht übergeben werden konnte. Auf dem Rücktransport nach Helsinki verschwand die Wertsendung unter ungeklärten Umständen. In der Folge zahlte die Winterthur Schweizerische Versicherungs-Gesellschaft (im Folgenden: die Klägerin) der UBS eine Entschädigung von CHF 1'237'200.--. B. Am 16. November 1998 machte die Klägerin beim Handelsgericht Regressansprüche gegen die Beklagte geltend und beantragte, diese sei zu verpflichten, CHF 1'237'200.-- nebst Zins zu 5% seit dem 13. Dezember 1996 zu bezahlen. Mit Urteil vom 15. März 2001 verpflichtete das Handelsgericht des Kantons Zürich die Beklagte, der Klägerin Fr. 824'800.-- nebst 5% Zins seit dem 13. Dezember 1996 zu bezahlen; im Mehrbetrag wurde die Klage abgewiesen. C. Mit Berufung vom 3. Mai 2001 beantragt die Beklagte dem Bundesgericht, das Urteil des Handelsgerichtes des Kantons Zürich vom 15. März 2001 sei aufzuheben und die Klage abzuweisen; eventuell sei das Urteil aufzuheben und die Klage im Umfang von Fr. 155.85 gutzuheissen und im Mehrbetrag abzuweisen; subeventuell sei das Urteil aufzuheben und zur Neubeurteilung, allenfalls zur Durchführung eines Beweisverfahrens, an die Vorinstanz zurückzuweisen. Die Klägerin beantragt die Abweisung der Berufung. Das Handelsgericht hat auf eine Stellungnahme verzichtet. Mit Beschluss vom 13. Oktober 2001 hat das Kassationsgericht des Kantons Zürich eine gleichzeitig erhobene kantonale Nichtigkeitsbeschwerde abgewiesen, soweit darauf einzutreten war.