Sachverhalt:
A. Das Strafgericht des Kantons Zug verurteilte Rechtsanwalt X._ am 18. Dezember 2006 wegen qualifizierter Geldwäscherei zu neun Monaten Gefängnis, unter Gewährung des bedingten Strafvollzugs bei einer Probezeit von zwei Jahren, und zu einer Busse von Fr. 20'000.--. In einem Fall sprach es ihn vom Vorwurf der qualifizierten Geldwäscherei frei.
B. Auf die Berufung von X._ bestätigte das Obergericht des Kantons Zug am 29. Oktober 2008 den erstinstanzlichen Schuldspruch. Zusätzlich hob es den Freispruch auf und sprach X._ auch in diesem Punkt der qualifizierten Geldwäscherei schuldig. Es verurteilte ihn zu einer Freiheitsstrafe von 10 Monaten, unter Gewährung des bedingten Strafvollzugs bei einer Probezeit von zwei Jahren, sowie zu einer unbedingten Geldstrafe von 60 Tagessätzen zu Fr. 400.--.
C. Gegen dieses Urteil erhebt X._ Beschwerde in Strafsachen. Er beantragt, er sei von Schuld und Strafe freizusprechen. Eventualiter sei die Sache zur neuen Entscheidung an die Vorinstanz zurückzuweisen.
D. Das Obergericht des Kantons Zug reichte mit Schreiben vom 11. Mai 2009 seine Vernehmlassung ein. Es beantragt, die Beschwerde sei abzuweisen. Die Staatsanwaltschaft des Kantons Zug beantragt mit Eingabe vom 2. Juni 2009 ebenfalls die Abweisung der Beschwerde.

Erwägungen:
1. Die Vorinstanz legt ihrer Verurteilung folgenden Sachverhalt zugrunde: Am 22. April 1997 stellte die A._ AG zwei Checks über 1 Mio DEM und 2 Mio DEM aus. Die Gelder zur Deckung der Checks stammen aus dem Anlagebetrug der B._ AG. Der Beschwerdeführer erhielt beide Checks von seinem Klienten C._, welchen er seit 1992 anwaltlich vertrat. Beide Checks waren mit einem Blankoindossament versehen. Der Beschwerdeführer reichte den Check über 2 Mio DEM der D._ Bank am 28. April 1997 zur Gutschrift auf den Konten der Offshore-Gesellschaft E._ AG, deren Direktor er war, ein. Am selben Tag übermittelte er der F._ Bank den Check über 1 Mio DEM zur Gutschrift auf die genannten Konten.
Am 15. Mai 1997 stellte die A._ AG zugunsten der E._ AG einen dritten Check über 1'241'455.-- DEM aus. Die Vermögenswerte zur Deckung dieses Checks stammen ebenfalls aus dem Anlagebetrug zum Nachteil der B._ AG-Anleger.
Am 20. Mai 1997 fanden zwei Treffen zwischen C._ und der F._ Bank bzw. der D._ Bank in Anwesenheit des Beschwerdeführers statt. Mit Schreiben vom 26. Mai 1997 sandte der Beschwerdeführer der F._ Bank den Check über 1'241'455.-- DEM zur Gutschrift. Nach einem Telefonat zwischen der F._ Bank und dem Beschwerdeführer vom 30. Mai 1997 retournierte die BPG den Check an den Beschwerdeführer. Im Begleitschreiben begründete die Bank die Rücksendung mit der "Vermeidung eines Schadens". Der Beschwerdeführer wurde gebeten, trotz des persönlichen Treffens vom 20. Mai 1997 der F._ Bank eine Erklärung einzureichen, welche sich über die Herkunft der Vermögenswerte seines Klienten C._ und über den Zweck der Überweisung äusserte. Der Beschwerdeführer reichte die verlangte Erklärung nicht ein, sondern kündigte die Callgeldanlage bei der F._ Bank mit Schreiben vom 3. Juni 1997. Den von der F._ Bank retournierten Check übergab er am selben Tag der D._ Bank zur Gutschrift.
Nach der Einlösung der Checks wechselte der Beschwerdeführer am 16. Juni 1997 den Betrag von 2 Mio DEM und am 7. Juli 1997 jenen über 1'241'455.-- DEM bei der Bank D._ Bank in Schweizer Franken. Am 11. Juli 1997 liess er sich von ihr Fr. 2'516'000.-- bar auszahlen. Dieses Geld händigte er gleichentags C._ aus. Am 5. Juni 1997 wechselte der Beschwerdeführer den Betrag von 1 Mio DEM bei der F._ Bank in Schweizer Franken. Nach der Kündigung der F._ Bank- Konten erhielt er einen Check über den Betrag von Fr. 835'065.25. Diesen versah er mit seinem Indossament und sandte ihn ungefähr am 19. Juni 1997 an den Treuhänder G._ nach Liechtenstein. Er gab ihm den Auftrag, den Check auf den Namen seiner [des G._ ] Treuhandgesellschaft H._ AG einzulösen und wies ihn an, das Geld dort einige Tage treuhänderisch für die E._ AG liegen zu lassen. Am 10. Juli 1997 liess sich der Beschwerdeführer von G._ das Geld gegen Quittung bar auszahlen und händigte es gleichentags C._ aus.
2. 2.1 Der Beschwerdeführer bringt vor, die Vorinstanz habe das Willkürverbot nach <ref-law> sowie das Verbot der "reformatio in peius" verletzt. Die erste Instanz habe ihn vom Vorwurf der Geldwäscherei bezüglich des Checks über DEM 1'241'455.-- freigesprochen. Dieser Freispruch sei in Rechtskraft erwachsen, da er von ihm selbst und der Staatsanwaltschaft unangefochten blieb. Trotzdem habe die Vorinstanz den Freispruch überprüft und aufgehoben. Dem Verbot der "reformatio in peius" komme Verfassungsrang zu. Soweit es aus dem kantonalen Prozessrecht hergeleitet werde, habe die Vorinstanz § 70 der Strafprozessordnung für den Kanton Zug vom 3. Oktober 1940 (BGS 321.1) willkürlich angewendet. Entgegen der Auffassung der Vorinstanz liege keine mit der zitierten kantonalen Rechtsprechung (GVP 1979/1980, S. 109) vergleichbare Situation vor. Eine Beurteilung der beiden angefochtenen Schuldsprüche sei unabhängig vom nicht angefochtenen Teil des Urteils möglich. Zwar verbiete § 70 StPO/ZG eine "reformatio in peius" nicht ausdrücklich, indessen gebiete eine verfassungsmässige Auslegung der Bestimmung die Beachtung dieses Grundsatzes.
2.2 Die Vorinstanz führt zum Verbot der reformatio in peius aus, für die Berufungsinstanz sei die Berufungsbeschränkung auf Teilaspekte nur insoweit verbindlich, als sich die angefochtenen Punkte aus materiell-rechtlichen Überlegungen unabhängig von den übrigen, nicht angefochtenen Teilen des Urteils begründen liessen. Beim Beschwerdeführer sei der Freispruch vom Vorwurf der qualifizierten Geldwäscherei ebenfalls zu überprüfen, da er materiell eng mit den anderen Vorwürfen zusammenhänge (angefochtenes Urteil S. 8). In ihrer Vernehmlassung weist sie darauf hin, dass nach der kantonalen Gerichtspraxis eine reformatio in peius zulässig sei. Die Vorwürfe bezüglich der drei Checks wiesen einen engen Zusammenhang auf, so dass auch der Freispruch im Zusammenhang mit dem Check vom 15. Mai 1997 über DEM 1'241'455.-- zu überprüfen sei. Die Beschwerdegegnerin macht in ihrer Vernehmlassung zu diesem Punkt keine Ausführungen.
2.3 Das Verbot der reformatio in peius, wonach unter anderem nicht angefochtene Punkte eines Urteils nicht zu Lasten des Verurteilten abgeändert werden dürfen, ergibt sich primär aus dem kantonalen Prozessrecht. Es zählt nicht zu den verfassungsmässigen Rechten des Bundes oder der Kantone und lässt sich nicht aus der EMRK herleiten. Die Missachtung dieses Grundsatzes ist unter dem Gesichtswinkel der Willkür zu prüfen (vgl. <ref-ruling> E. 2.1.1 S. 419 mit Hinweis; <ref-ruling> E. 3/c S. 115 Urteil 6B_411/2007 vom 2. November 2007 E. 1.3).
Nach der bundesgerichtlichen Praxis liegt Willkür in der Rechtsanwendung vor, wenn der angefochtene kantonale Entscheid offensichtlich unhaltbar ist, mit der tatsächlichen Situation in klarem Widerspruch steht, eine Norm oder einen unumstrittenen Rechtsgrundsatz krass verletzt oder in stossender Weise dem Gerechtigkeitsgedanken zuwiderläuft. Das Bundesgericht hebt einen Entscheid jedoch nur auf, wenn nicht bloss die Begründung, sondern auch das Ergebnis unhaltbar ist. Dass eine andere Lösung ebenfalls als vertretbar oder gar als zutreffender erscheint, genügt nicht (<ref-ruling> E. 1.2 S. 177; <ref-ruling> E. 3.1 S. 473 f., je mit Hinweisen).
2.4 Die Strafprozessordnung des Kantons Zug kennt kein ausdrückliches Verbot der reformatio in peius. Sie erlaubt die reformatio in peius auch in Fällen, in denen nur der Angeklagte oder die Staatsanwaltschaft zugunsten des Angeklagten ein Rechtsmittel einlegt (vgl. Urteil 6S.170/2000 vom 19. Juni 2000 E. 4b; HAUSER/SCHWERI/HARTMANN, Schweizerisches Strafprozessrecht, 6. Aufl., Basel 2005, § 98 N. 3). § 70 StPO/ZG ist gemäss der kantonalen Rechtsprechung dahingehend auszulegen, dass eine Teilanfechtung für die Berufungsinstanz nur soweit verbindlich ist, als sich die angefochtenen Punkte aus materiell-rechtlichen Überlegungen unabhängig von den übrigen, nicht angefochtenen Teilen des Urteils beurteilen lassen (Gerichts- und Verwaltungspraxis des Kantons Zug 1979/1980, S. 109).
Die drei dem Beschwerdeführer zur Last gelegten Delikte weisen einen engen sachlichen und zeitlichen Zusammenhang auf. Sie betreffen drei Checks, welche innert eines knappen Monats von derselben Gesellschaft ausgestellt wurden und deren Gelder aus dem selben Anlagebetrug stammen. Mit allen Checks nahm der Beschwerdeführer gleichartige Handlungen in den Monaten April bis Juli 1997 vor. Er erhielt sie von seinem Klienten C._, beteiligte sich an Gesprächen mit ihm und zwei Banken zur Frage der Herkunft der Gelder, reichte die Checks diesen Banken zur Gutschrift ein, wechselte die Gelder nach der Einlösung der Checks in Schweizer Franken, hob die Gelder bar ab und händigte sie seinem Klienten C._ aus. Die Vorinstanz handelt nicht schlechterdings unvertretbar, wenn sie unter Berücksichtigung des engen sachlichen und zeitlichen Zusammenhangs der Vorwürfe auch den Freispruch überprüft. Eine willkürliche Anwendung von § 70 StPO/ZG ist damit nicht ersichtlich, weshalb die Beschwerde diesbezüglich abzuweisen ist.
3. 3.1 Der Beschwerdeführer macht geltend, die Vorinstanz habe den Grundsatz des rechtlichen Gehörs nach <ref-law> verletzt. Sie habe ihm keine Möglichkeit eingeräumt, sich zur Aufhebung des Freispruchs bezüglich des Checks vom 15. Mai 1997 und zur Verschärfung der Sanktion zu äussern. Er habe keine Veranlassung gehabt, dazu Stellung zu nehmen, nachdem weder er noch die Staatsanwaltschaft diesen Punkt angefochten hätten.
3.2 In ihrer Stellungnahme führt die Vorinstanz aus, der Vorwurf bezüglich des Checks vom 15. Mai 1997 sei dem Beschwerdeführer bekannt gewesen. Er sei ihm im Rahmen der Schlusseinvernahme vorgehalten worden und habe Bestandteil der Anklageschrift der Staatsanwaltschaft gebildet. Der Beschwerdeführer habe dazu in der Untersuchung, der Vernehmlassung zur Anklage und in der erstinstanzlichen Verhandlung Stellung genommen. Es sei daher nicht erforderlich gewesen, ihn in der zweitinstanzlichen Verhandlung nochmals ausdrücklich darauf aufmerksam zu machen, wenn er nichts mehr hierzu von sich aus habe ausführen wollen.
3.3 Gemäss <ref-law> haben die Parteien Anspruch auf rechtliches Gehör. Der Betroffene hat das Recht, sich vor Erlass eines in seine Rechtsstellung eingreifenden Entscheids zur Sache zu äussern (<ref-ruling> E. 6 S. 341; <ref-ruling> E. 2b S. 56 je mit Hinweis). Indessen ist es zur Beachtung des rechtlichen Gehörs nicht erforderlich, dass die Vorinstanz bereits vor der Ausfällung des Urteils zur Würdigung der Beweise Stellung bezieht und ihre rechtlichen Argumente darlegt. Es steht fest, dass der Check vom 15. Mai 1997 im Rahmen der Obergerichtsverhandlung kein Thema war und diesbezüglich keine neuen Fragen gestellt, Aussagen getätigt oder Beweismittel eingereicht wurden (vgl. Vorakten act. 13/1 Protokoll der Hauptverhandlung vom 30. September 2008).
3.4 Der Beschwerdeführer bringt zu Recht vor, dass ihn die Vorinstanz vor der Ausfällung ihres Urteils nicht darauf aufmerksam gemacht hat, dass sie den Freispruch der ersten Instanz überprüft und womöglich einen weiteren Schuldspruch zu seinen Ungunsten fällt, welcher sich in einer höheren Strafe niederschlägt. Auch wenn eine reformatio in peius nach kantonalem Prozessrecht grundsätzlich zulässig ist, so ist der Beschwerte von derjenigen Instanz, welche die Verschlechterung zu seinen Lasten prüft, vorgängig darauf aufmerksam zu machen. Der Beschwerdeführer ist nicht gehalten, zu Themen Ausführungen zu machen, welche für ihn, soweit er dies erkennen kann, nicht mehr Prozessgegenstand sind. Die Vorinstanz hat den Anspruch des Beschwerdeführers auf rechtliches Gehör verletzt. Das Urteil ist demzufolge aufzuheben und an die Vorinstanz zurückzuweisen.
4. 4.1 Der Beschwerdeführer rügt, die Vorinstanz habe die Beweise willkürlich gewürdigt, entlastende Tatsachen nicht berücksichtigt, willkürliche Schlussfolgerungen gezogen und den Grundsatz "in dubio pro reo" verletzt (Ziff. 28 bis 49 der Beschwerdeschrift). Soweit die Rügen den Check vom 15. Mai 1997 betreffen, ist darauf nicht einzugehen, da in diesem Punkt eine Rückweisung an die Vorinstanz erfolgt (vgl. E. 3.). Die Vorinstanz muss den Sachverhalt insoweit unter Berücksichtigung der vom Beschwerdeführer im Rahmen des rechtlichen Gehörs ebenfalls vorgebrachten Einwände erneut prüfen.
4.2 Gemäss <ref-law> ist in der Begründung der Beschwerde in gedrängter Form darzulegen, inwiefern der angefochtene Akt Recht verletzt. Das Bundesgericht prüft nur klar und detailliert erhobene und belegte Rügen. Auf rein appellatorische Kritik am angefochtenen Entscheid tritt es nicht ein. Es prüft die Verletzung des Willkürverbots nur insofern, als eine solche Rüge in der Beschwerde vorgebracht und begründet worden ist (<ref-law>). Der Beschwerdeführer muss sich dazu mit den Entscheidgründen der Vorinstanz auseinandersetzen und präzise angeben, worin er die Rechtsverletzung erblickt bzw. inwiefern der Entscheid an einem qualifizierten und offensichtlichen Mangel leidet (<ref-ruling> E. 2.1 und 2.2 S. 245 f.; <ref-ruling> E. 1.3 S. 261 f.; je mit Hinweisen).
Die Einwendungen in der Beschwerde sind zur Hauptsache rein appellatorischer Natur (vgl. unter anderem Beschwerdeschrift Ziff. 29 inkl. Ziff. 48 und Ziff. 52 zur Frage des subjektiven Tatbestandes bzw. des "eigenen Antriebs" im Sinne des Inkaufnehmens; Ziff. 30 zur Frage der "due diligence" und zur Würdigung der Aussage des Zeugen von I._; Ziff. 35 zum Widerspruch in den Aussagen von C._ über die Herkunft der Gelder; Ziff. 36 zur Beweiswürdigung bezüglich der Aussagen des Beschwerdeführers; Ziff. 42 zur Frage des Eventualvorsatzes; Ziff. 43 zum Eindruck der Zeugen von I._ und K._ von C._; Ziff. 48 zur Frage der Barbezüge von C._ und der Papierspur; Ziff. 49 zur Frage der Rückzahlung der Gelder im Dezember 1997; Ziff. 52 zur Frage der Papierspur). Darauf ist nicht einzugehen. Zu prüfen sind mithin nur die in der Beschwerde ausreichend begründeten Rügen. Diese beziehen sich vorwiegend auf den subjektiven Tatbestand.
4.3 Der Beschwerdeführer bringt vor, die Vorinstanz habe sich nicht mit der entlastenden Aussage des Zeugen K._ befasst, welcher an der Besprechung vom 20. Mai 1997 als Vertreter der Bank anwesend war. Sie sei deshalb in Willkür verfallen (Ziff. 30 der Beschwerdeschrift).
Es ist zutreffend, dass die Vorinstanz die Aussage von K._ (Vorakten act. 4/3/6) in ihrer Urteilsbegründung nicht erwähnt. Indessen hat sie die wesentlichen Punkte ihrer Beweiswürdigung dargelegt und sich zum objektiven Tatbestand vorwiegend auf den unbestrittenen äusserlichen Ablauf betreffend Checkeinlösung und zum subjektiven Tatbestand auf die Aussagen des Beschwerdeführers selbst abgestützt. Sie muss sich nicht ausdrücklich mit jeder tatbeständlichen Behauptung und jedem rechtlichen Einwand auseinandersetzen. Vielmehr darf sie sich auf die für den Entscheid wesentlichen Gesichtspunkte beschränken (<ref-ruling> E. 3.1 S. 277 mit Hinweisen). Dass sie sich nicht mit der Aussage von K._ befasst hat, erweist sich nicht als willkürlich, zumal nicht substantiiert dargelegt wird, was diese zur Entlastung des Beschwerdeführers beitragen könnte. Die Rüge erweist sich als unbegründet.
4.4 Der Beschwerdeführer macht geltend, die Schlussfolgerungen der Vorinstanz, wonach er die verbrecherische Herkunft der Gelder in Kauf genommen habe, seien willkürlich. Er bringt vor, die Vorinstanz habe nicht ausgeführt, welche Abklärungen zur Herkunft des Geldes er hätte treffen sollen. Möglich sei einzig eine Erkundigung beim Aussteller der Checks, L._ gewesen, welcher gemäss den Erwägungen der Vorinstanz nichts von der verbrecherischen Herkunft der Gelder habe wissen müssen. Deshalb könne dieses Wissen auch vom Beschwerdeführer nicht verlangt werden. Nicht jede Finanztransaktion an eine Offshore-Gesellschaft sei geeignet, einen Verdacht auf Geldwäscherei zu begründen (Ziff. 33 der Beschwerdeschrift).
Die Beschwerdegegnerin führt in ihrer Vernehmlassung aus, der Beschwerdeführer hätte durch eine Rückfrage beim ihm bekannten M._ erfahren können, dass die Geldmittel für die beiden Checks über 1 Mio bzw. 2 Mio DEM, welche an die N._ AG ausgestellt waren, betrügerisch beschafft worden seien. Es sei nicht willkürlich, weitere Abklärungen zu verlangen. Insbesondere hätte bereits ein Blick ins Handelsregister ergeben, dass M._ für die N._ AG nicht zeichnungsberechtigt war.
Alleine aus den fehlenden Ausführungen der Vorinstanz zu weiteren möglichen Abklärungen den Schluss zu ziehen, sie habe daraus in willkürlicher Weise eine Inkaufnahme der verbrecherischen Herkunft der Gelder bejaht, ist verfehlt. Nebst mündlichen Erkundigungen wäre beispielsweise ein Einverlangen von schriftlichen Unterlagen zur Herkunft der Gelder möglich gewesen. Überdies zielt die Rüge des Beschwerdeführers lediglich auf einen Teilaspekt zum subjektiven Tatbestand ab. Die Vorinstanz hat detailliert begründet, weshalb sie den subjektiven Tatbestand als gegeben erachtet (vgl. E. 4.7.2). Auch wenn die vorinstanzliche Urteilsbegründung keine Ausführungen zu den möglichen Abklärungen enthält, welche der Beschwerdeführer hätte vornehmen können, erweisen sich die Schlussfolgerungen im Ergebnis nicht als schlechterdings unhaltbar und sind nicht zu beanstanden.
4.5 Der Beschwerdeführer rügt die unterschiedliche Beurteilung der Delikte der Mitangeklagten O._ und L._ im Vergleich zu den ihm vorgeworfenen Taten (Beschwerdeschrift Ziff. 34, 43, 45 bis 47).
Er übersieht dabei, dass den Mitangeklagten L._ und O._ in tatsächlicher Hinsicht andere Tathandlungen zur Last gelegt werden als ihm selbst. Dies führt dazu, dass weder der objektive noch der subjektive Tatbestand gleich zu beurteilen sind. Aus den Entscheiden betreffend die Mitangeklagten kann der Beschwerdeführer nichts zu seinen Gunsten ableiten. Die Rüge ist insoweit unbegründet.
4.6 Der Beschwerdeführer macht geltend, die Vorinstanz habe eine Passage aus dem Urteil des Landgerichts Berlin (act. HD 5/4/3 S. 7) falsch zitiert, indem sie C._ mit dem Mitangeklagten O._ verwechselt habe. Das Wort "er" im zitierten Satz (angefochtenes Urteil S. 30 Ziff. 2.4.4) beziehe sich auf den Mitangeklagten O._. C._ habe gemeint, der Beschwerdeführer sei als enger Vertrauter des O._ in gleicher Weise wie O._ über die Herkunft der Gelder informiert gewesen. Zudem habe die Vorinstanz dieses Urteil nicht zu seinen Lasten verwenden dürfen, da er dort keine Verfahrensrechte gehabt habe (Ziff. 44 der Beschwerdeschrift).
Die Vorinstanz hat im Rahmen der Prüfung des subjektiven Tatbestandes ausgeführt, "nur am Rande sei vermerkt, dass das Landgericht Berlin in seinem rechtskräftigen Urteil gegen C._ festhielt, der Angeklagte (C._ ) sei bei den über die Konten der E._ AG abgewickelten Zahlungsvorgängen vom Beschuldigten X._ unterstützt worden. Dieser sei als enger Vertrauter des O._ laut den Angaben von C._ zumindest in gleicher Weise wie er [C._ ] über die Herkunft der Gelder informiert gewesen (HD 5/4/3, S. 7)."
Die fragliche Erwägung wurde von der Vorinstanz "nur am Rande" beigefügt und ist damit offensichtlich nicht entscheiderheblich. Daher erübrigt sich, auf die dagegen erhobenen Einwände einzutreten.
Die fragliche Erwägung wurde von der Vorinstanz "nur am Rande" beigefügt und ist damit offensichtlich nicht entscheiderheblich. Daher erübrigt sich, auf die dagegen erhobenen Einwände einzutreten.
4.7 4.7.1 Der Beschwerdeführer rügt unter dem Titel "willkürliche Beweiswürdigung" (Ziffer 28 der Beschwerdeschrift) und der Verletzung des Grundsatzes "in dubio pro reo" (Ziffer 41 der Beschwerdeschrift), die Vorinstanz sei in willkürlicher Weise von einem "Eventualvorsatz" ausgegangen. Er macht sinngemäss geltend, er habe die Delikte entgegen den Ausführungen der Vorinstanz nicht in Kauf genommen. Ihm fehle ein Tatmotiv. Das vereinnahmte Honorar von Fr. 20'000.-- stelle kein Motiv für eine Geldwäsche von DEM 4'241'455.-- dar, weil es nicht nur sein Verwaltungsratshonorar, sondern den Zeitaufwand für die Rechts- und Steuerberatung, die Due Diligence und die Auslagen abdecke. Er habe schon damals erfolgreich eine Anwaltskanzlei geführt und keinen Grund gehabt, seinen guten Ruf als Anwalt bzw. sein Anwaltspatent aufs Spiel zu setzen.
4.7.2 Die Vorinstanz führt zum subjektiven Tatbestand im Einzelnen aus, dem Beschwerdeführer habe gemäss seinen Aussagen der Firmenname A._ AG nichts gesagt. Trotzdem habe er Checks entgegengenommen, eingelöst, in eine andere Währung gewechselt, einen Check ins Ausland gesandt und den grössten Teil des Geldes an C._ in bar ausgehändigt. Der Beschwerdeführer habe die Herkunft der Gelder nicht abgeklärt und widersprüchliche Angaben darüber gemacht. Einmal habe er gesagt, sie stammten aus dem Verkauf privater Beteiligungen seines Klienten. Der Klient habe seine Anteile an der P._ GmbH verkaufen und sich auf den Lebensabend etwas Ruhe mit seiner neuen Familie gönnen wollen. Ein anderes Mal habe er ausführen lassen, er habe seinem Klienten bei Finanztransaktionen helfen wollen. C._ habe das bei der A._ AG angelegte Geld abziehen und anderweitig investieren wollen, um möglichen Ansprüchen aufgrund der komplizierten familiären Struktur entgegen zu wirken.
Dem Beschwerdeführer hätten sich spätestens nach der Besprechung bei der F._ Bank vom 20. Mai 1997 aufgrund der dort zutage getretenen widersprüchlichen Angaben des C._ über die Herkunft der Gelder, des fehlenden Zusammenhangs zwischen der Firma A._ AG und der P._ GmbH und weil ihm der Firmenname A._ AG nichts sagte, Zweifel aufgedrängt, weswegen er Abklärungen hätte vornehmen müssen. Die Transaktionen seien im Lichte der von C._ angegebenen Gründe nicht plausibel. Die beiden Checks vom 22. April 1997 seien blanko indossiert gewesen. Damit wären bei den ehe- und erbrechtlichen Motiven des C._ weitere Transaktionen nicht mehr erforderlich gewesen, da durch das Blankoindossament die Papierspur verwischt worden sei. Beim Motiv der Unzufriedenheit über die Geldanlage bei der A._ AG hätte ein Ausstellen der Checks direkt zugunsten von C._ bzw. der E._ AG genügt. Es sei nicht ersichtlich, weshalb auf den Checks die Gesellschaft N._ AG dazwischengeschaltet worden sei. Dies habe auch der Beschwerdeführer bemerken müssen.
Spätestens mit der Retournierung des Checks über DEM 1'241'455.-- und dem Schreiben der F._ Bank, wonach sie weitere Angaben über die Herkunft der Vermögenswerte von C._ verlangte, hätte der Beschwerdeführer gemäss den weiteren Ausführungen der Vorinstanz im Zusammenhang mit allen drei Checks Abklärungen über die Herkunft der Gelder tätigen müssen. Stattdessen habe er innert weniger Tage ungewöhnliche Transaktionen durchgeführt. Er habe Währungswechsel verlangt, Geld bar abgehoben, dieses Geld C._ ausgehändigt, einen Check indossiert und an einen Treuhänder ins Ausland geschickt mit der Weisung, diesen einzulösen und das Geld einige Tage dort treuhänderisch liegen zu lassen. Kurze Zeit später habe er das vom Treuhänder bar abgehobene Geld entgegengenommen und gleichentags C._ übergeben. Sein Verhalten könne nur damit erklärt werden, dass er es als langjährig tätiger Anwalt für möglich hielt, dass die Vermögenswerte aus einer Straftat stammten und er dies aus Gleichgültigkeit in Kauf nahm. Die Rückzahlung von CHF 3.4 Mio an die A._ AG vermöge am Vorliegen des Eventualvorsatzes nichts zu ändern, da die A._ AG den Gegenwert der Checks erst viel später, nämlich am 17. Dezember 1997 erhalten habe und der Tatbestand der Geldwäscherei als abstraktes Gefährdungsdelikt keinen Erfolg, d.h. keine vereitelte Ermittlung der Herkunft, Auffindung oder Einziehung von Vermögenswerten, verlange.
4.7.3 Gemäss <ref-law> begeht ein Verbrechen oder Vergehen vorsätzlich, wer die Tat mit Wissen und Willen ausführt (Satz 1). Vorsätzlich handelt bereits, wer die Verwirklichung der Tat für möglich hält und in Kauf nimmt (Satz 2). Was der Täter weiss, will und in Kauf nimmt, betrifft nach der bundesgerichtlichen Rechtsprechung eine innere Tatsache und ist Tatfrage. Rechtsfrage ist hingegen, unter welchen tatsächlichen Voraussetzungen bewusste Fahrlässigkeit, Eventualvorsatz oder direkter Vorsatz gegeben ist (vgl. <ref-ruling> E. 4.1. S. 17; <ref-ruling> E. 8.5 S. 62).
4.7.4 Die Vorinstanz hat mit ihren eingehenden Ausführungen die Schlussfolgerung, der Beschwerdeführer habe die verbrecherische Herkunft der Vermögenswerte in Kauf genommen, willkürfrei begründet. Der Einwand des Beschwerdeführers, er habe kein "Tatmotiv" gehabt, geht an der Sache vorbei, da ein Tatmotiv keine Voraussetzung des subjektiven Tatbestandes der Geldwäscherei nach <ref-law> bildet. Eine willkürliche Beweiswürdigung ist nicht ersichtlich, soweit die Beschwerde überhaupt den Begründungsanforderungen genügt (vgl. E. 4.2). Die Rüge ist unbegründet.
5. 5.1 Der Beschwerdeführer rügt unter dem Titel "willkürliche Schlussfolgerungen", das Bundesgesetz über die Bekämpfung der Geldwäscherei und der Terrorismusfinanzierung im Finanzsektor (Geldwäschereigesetz, GwG, SR 955.0) sei im Jahr 1997 noch nicht in Kraft gewesen, weshalb er nicht nach diesem Massstab zu beurteilen sei (Beschwerdeschrift Ziff. 32). Im gleichen Zusammenhang (Beschwerdeschrift Ziff. 51) macht er eine Bundesrechtsverletzung geltend. Er bringt vor, die Vorinstanz habe von ihm zu Unrecht weitere Abklärungen verlangt. Es hätten zur Zeit der Tathandlung keine besonderen Abklärungspflichten bestanden, da <ref-law> noch nicht in Kraft gewesen sei.
5.2 Die Vorinstanz hat den Sorgfaltsmassstab anhand der Angaben, welche der Beschwerdeführer von seinem Klienten C._ erhalten hat, dem ungewöhnlichen Ablauf der verschiedenen Finanz-Transaktionen, der Höhe der transferierten Beträge und der langjährigen beruflichen Erfahrung des Beschwerdeführers als Anwalt beurteilt.
Entgegen den Vorbringen des Beschwerdeführers ist das Geldwäschereigesetz für den Tatbestand der Geldwäscherei nur insoweit relevant, als es nach Art. 6 i.V.m. <ref-law> Prüfungs- und Meldepflichten für Rechtsanwälte begründet, die eine Garantenstellung bei Unterlassungsdelikten betreffen (vgl. Jürg-Beat Ackermann, in: Kommentar Einziehung organisiertes Verbrechen Geldwäscherei, Band I, 1998, N. 385). Vorgeworfen werden dem Beschwerdeführer jedoch aktive Handlungen, weshalb eine allfällige Garantenpflicht unerheblich ist. Die Vorinstanz hat die Delikte auch nicht nach dem Geldwäschereigesetz beurteilt, sondern den Sorgfaltsmassstab verlangt, welcher dem Beschwerdeführer aufgrund seiner persönlichen Umstände zugemutet werden darf und sich aus dem bereits zur Tatzeit in Kraft stehenden <ref-law> ergibt. Die Beschwerde ist in diesem Punkt abzuweisen.
6. 6.1 Der Beschwerdeführer rügt, die Vorinstanz habe zu Unrecht einen schweren Fall im Sinne von <ref-law> bejaht und damit Bundesrecht verletzt.
6.2 Die Beschwerdegegnerin geht in ihrer Vernehmlassung davon aus, dass die Anforderungen für die Annahme eines schweren Falles nicht überspannt werden dürfen. Die Vorinstanz habe zu Recht einen schweren Fall angenommen. Dieser könne auch vorliegen, wenn jemand einmalig Vermögenswerte in Millionenhöhe wasche.
6.3 Ob die Taten des Beschwerdeführers als schwerer Fall im Sinne von <ref-law> zu werten sind, kann erst geprüft werden, wenn auch der für den dritten Check vom 15. Mai 1997 massgebende Sachverhalt nach Gewährung des rechtlichen Gehörs von der Vorinstanz festgestellt ist. Diese Frage ist offen zu lassen.
7. 7.1 Der Beschwerdeführer rügt, die Strafzumessung der Vorinstanz verletze Bundesrecht. Sie habe die Verletzung des Beschleunigungsgebots zu Unrecht als leicht gewertet. Zudem habe die Vorinstanz die mit der bedingten Freiheitsstrafe verbundene Geldstrafe nach <ref-law> zu Unrecht unbedingt ausgesprochen.
7.2 Auch diese Rügen gegen die Strafzumessung sind im vorliegenden Fall nicht zu beurteilen, weil das Strafmass vom Ausgang des neuen kantonalen Verfahrens abhängt.
8. Der Beschwerdeführer wird im Rahmen seines Unterliegens kostenpflichtig (<ref-law>). Soweit der Beschwerdeführer obsiegt, hat er Anspruch auf Parteientschädigung, die ihm vom Kanton Zug auszurichten ist.

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird teilweise gutgeheissen, das Urteil des Obergerichts des Kantons Zug vom 29. Oktober 2008 aufgehoben und die Sache zur neuen Entscheidung an die Vorinstanz zurückgewiesen. Im Übrigen wird die Beschwerde abgewiesen, soweit darauf einzutreten ist.
2. Die Gerichtskosten von 2'000.-- werden dem Beschwerdeführer auferlegt.
3. Der Kanton Zug hat den Beschwerdeführer für das bundesgerichtliche Verfahren mit Fr. 1'500.-- zu entschädigen.
4. Dieses Urteil wird den Parteien und dem Obergericht des Kantons Zug, Strafrechtliche Abteilung, schriftlich mitgeteilt.
Lausanne, 10. Juni 2009
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Die Gerichtsschreiberin:
Favre Koch