Sachverhalt: A. Die X._ AG (Beschwerdeführerin; Verkäuferin) mit Sitz in Basel und die Y._ SA (Beschwerdegegnerin; Käuferin) mit Sitz in Spanien schlossen am 12. Dezember 2000 einen Vertrag über die Lieferung einer Abfüll- und Verpackungsanlage. Der Kaufpreis der gesamten Anlage betrug Pts 247'278'337.-- (entsprechend EUR 1'486'172.74). Die Anlage umfasste zehn Maschinen sowie die Transport- und Verbindungssysteme zwischen diesen. Die Beschwerdeführerin hatte die Verpackungslinie zu installieren und in Betrieb zu setzen. Nach der Installation der Anlage wollte die Beschwerdeführerin einen Abnahmelauf durchführen, wobei sich die Parteien über die zu erreichende Produktionsleistung uneinig waren. Die Beschwerdegegnerin bestand im Wesentlichen auf einer Leistungsfähigkeit der gesamten Anlage von 180 Flacons pro Minute. Die Beschwerdeführerin erklärte, dass eine solche Gesamtleistung weder möglich noch vereinbart sei. Sie unternahm diverse Versuche, die deutlich unter dem Wert von 180 Flacons pro Minute liegende Leistung zu erhöhen. Am 23. März 2003 erklärte die Beschwerdegegnerin die Auflösung des Vertrags und forderte die Rückzahlung des bereits bezahlten Kaufpreises nebst Schadenersatz. Am 9. Februar 2004 leitete die Beschwerdegegnerin die Betreibung ein. B. Mit Eingabe vom 5. August 2004 erhob die Beschwerdegegnerin Klage beim Zivilgericht Basel-Stadt. Sie beantragte, die Beschwerdeführerin zur Rückzahlung von EUR 495'390.91 zuzüglich 5 % Zins seit dem 22. Januar 2001 sowie zur Rückzahlung von EUR 495'390.91 zuzüglich 5 % Zins seit dem 19. November 2001, Zug um Zug gegen Rückgabe der von der Beschwerdeführerin gelieferten Maschinenanlage gemäss dem zwischen den Parteien geschlossenen Kaufvertrag vom 12. Dezember 2000, zu verurteilen. Zudem sei die Beschwerdeführerin zur Zahlung von EUR 110'393.48 zuzüglich 5 % Zins seit dem 25. März 2003, zur Zahlung von EUR 13'007.20 zuzüglich 5 % Zins seit dem 10. Februar 2004 sowie zur Zahlung von EUR 177'632.37 zuzüglich 5 % Zins seit dem 22. Juni 2004, Mehrforderung vorbehalten, zu verpflichten (Wandelung). Eventuell sei die Beschwerdeführerin zur Zahlung von EUR 1'301'450.77 zuzüglich 5 % Zins seit dem 1. Oktober 2001, zur Zahlung von EUR 13'007.20 zuzüglich 5 % Zins seit dem 10. Februar 2004 und zur Zahlung von EUR 177'632.37 zuzüglich 5 % Zins seit dem 22. Juni 2004, Mehrforderung vorbehalten, abzüglich der letzten Kaufpreisrate von EUR 495'390.91, zu verurteilen (Minderung). Die Beschwerdeführerin forderte ihrerseits widerklageweise den Restpreis sowie Entschädigungen. Sie beantragte, die Beschwerdegegnerin auf Bezahlung von EUR 731'675.19 nebst gestaffeltem Zins zu verurteilen, vorbehältlich einer Mehrforderung. Mit Urteil vom 8. November 2006 erkannte das Zivilgericht Folgendes: 1. In Gutheissung der Klage wird die Beschwerdeführerin zur Rückzahlung von EUR 495'390.91 zuzüglich 5 % Zins seit dem 22. Januar 2001, sowie zur Rückzahlung von EUR 495'390.91 zuzüglich 5 % Zins seit dem 19. September 2001, Zug um Zug gegen Rückgabe der von der Beschwerdeführerin gelieferten Maschinenanlage gemäss dem zwischen den Parteien geschlossenen Kaufvertrag vom 12. Dezember 2000; zur Zahlung von EUR 110'393.48 zuzüglich 5 % Zins seit dem 25. März 2003; zur Zahlung von EUR 13'007.20 zuzüglich 5 % Zins seit dem 10. Februar 2004; zur Zahlung von EUR 177'632.37 zuzüglich 5 % Zins seit dem 22. Juni 2004 an die Beschwerdegegnerin verurteilt. 2. Die Widerklage wird abgewiesen. Gegen dieses Urteil des Zivilgerichts gelangte die Beschwerdeführerin an das Appellationsgericht des Kantons Basel-Stadt. Sie beantragte, das Urteil des Zivilgerichts aufzuheben. Die Klage sei abzuweisen und die Beschwerdegegnerin widerklageweise zu verurteilen, ihr EUR 731'675.19 nebst gestaffeltem Zins zu bezahlen. Das Appellationsgericht bestätigte am 26. September 2008 das erstinstanzliche Urteil. C. Mit Beschwerde in Zivilsachen beantragt die Beschwerdeführerin, das Urteil des Appellationsgerichts vom 26. September 2008 aufzuheben. Die Klage sei abzuweisen und die Widerklage sei zur erneuten Entscheidung an das Appellationsgericht zurückzuweisen. Eventualiter seien die Klage und die Widerklage zur erneuten Entscheidung an das Appellationsgericht zurückzuweisen. Die Beschwerdegegnerin stellt das Begehren, die Beschwerde abzuweisen und das Urteil des Appellationsgerichts zu bestätigen. Das Appellationsgericht schliesst auf Abweisung der Beschwerde. D. Der Beschwerde wurde mit Präsidialverfügung vom 9. April 2009 superprovisorisch die aufschiebende Wirkung gewährt.