Sachverhalt:
A. Mit Urteil vom 3. Dezember 2008 bestätigte das Obergericht des Kantons Aargau zweitinstanzlich den Schuldspruch des Gerichtspräsidiums Lenzburg gegen Y._ wegen Überholens über eine Sicherheitslinie respektive Sperrfläche sowie Rechtsüberholens durch Ausschwenken und Wiedereinbiegen. Es verurteilte den Angeklagten zu einer Busse von Fr. 7'500.--, ersatzweise zu drei Tagen Freiheitsstrafe. In Ergänzung des erstinstanzlichen Entscheides ordnete das Obergericht an, auf die Mitteilung der Busse an das VOSTRA nach Eintritt der Rechtskraft des Urteils sei zu verzichten.
B. Die Staatsanwaltschaft des Kantons Aargau führt mit Eingabe vom 18. Dezember 2008 Beschwerde in Strafsachen. Sie ficht einzig den Verzicht auf eine VOSTRA-Mitteilung an.
C. Das Obergericht des Kantons Aargau hat am 30. Januar 2009 auf eine Vernehmlassung verzichtet. Y._ beantragt am 19. Februar 2009 Abweisung der Beschwerde.

Erwägungen:
1. Der sechste Titel des dritten Buches des Schweizerischen Strafgesetzbuches enthält in den Art. 365 bis 371 die Bestimmungen über das automatisierte Strafregister. <ref-law> regelt die Bearbeitung der Daten und die diesbezügliche Einsicht. Gestützt auf die Abs. 3 und 6 dieser Vorschrift sowie auf Art. 46a des Regierungs- und Verwaltungsorganisationsgesetzes vom 21. März 1997 (SR 172.010) hat der Bundesrat die Verordnung über das Strafregister (VOSTRA-Verordnung) vom 29. September 2006 (SR 331; in Kraft seit 1. Januar 2007) erlassen. Art. 3 der Verordnung hält in Ausführung von <ref-law> fest, welche Urteile in VOSTRA einzutragen sind. Gemäss Art. 3 Abs. 1 lit. c VOSTRA-Verordnung sind dies alle Verurteilungen wegen Übertretungen des StGB, des MStG oder anderer Bundesgesetze, wenn eine Busse von mehr als 5'000 Franken oder gemeinnützige Arbeit von mehr als 180 Stunden verhängt wird.
2. Die Vorinstanz führt aus, der in Anwendung von <ref-law> festgesetzte Bussenbetrag schlüssle die Komponenten des Verschuldens und der wirtschaftlichen Leistungsfähigkeit im Gegensatz zur Geldstrafe nicht auf. Weil indessen die Strafe unter anderem nach dem Verschulden bemessen werde, seien die im konkreten Fall auszufällende Busse, Ersatzfreiheitsstrafe oder die gemeinnützige Arbeit, welche an die Stelle der ausgesprochenen Busse treten könne, bezüglich des Verschuldens äquivalent. Diese Äquivalenz müsse auch für die beiden Obergrenzen nach Art. 3 Abs. 1 lit. c Ziff. 1 VOSTRA-Verordnung gelten. Weil das Verschulden bei einer mit Busse zu ahndenden Übertretung in der gleichzeitig mit der Busse auszufällenden Ersatzfreiheitsstrafe (<ref-law>) zum Ausdruck komme und aufgrund der Ersatzfreiheitsstrafe die gemeinnützige Arbeit zu berechnen sei, könne die in der VOSTRA-Verordnung bestimmte Bussenobergrenze nicht für sich alleine, sondern nur in Relation zu der in derselben Bestimmung aufgeführten maximal möglichen gemeinnützigen Arbeit für die Eintragung der Busse ausschlaggebend sein. Eine Freiheitsstrafe von drei Tagen entspreche zwölf Stunden gemeinnütziger Arbeit. Der absurden Konsequenz, dass die Busse im VOSTRA einzutragen wäre, die gemeinnützige Arbeit jedoch nicht, sei damit abzuhelfen, dass für die Eintragung nicht die Bussensumme, sondern die Ersatzfreiheitsstrafe ausschlaggebend sei, welche multipliziert mit dem Faktor 4 die Anzahl Stunden gemeinnütziger Arbeit ergebe. Ein Eintrag sei nur möglich, wenn sowohl die Bussensumme wie auch die Anzahl Stunden gemeinnütziger Arbeit die in der VOSTRA-Verordnung festgelegten Obergrenzen überschritten (vgl. angefochtenen Entscheid, S. 13 f. E. 6.4).
3. Nach Auffassung der Beschwerdeführerin verkennt die Vorinstanz den Charakter der Busse gemäss <ref-law> als blosse Geldsummensanktion, die im Gegensatz zur Geldstrafe nicht klar in eine Verschuldenskomponente und eine persönliche Finanzkomponente aufgeschlüsselt werden könne. Der Verordnungsgeber habe die beiden Eintragungskriterien gemäss Art. 3 Abs. 1 lit. c Ziff. 1 VOSTRA-Verordnung alternativ und unabhängig voneinander ausgestaltet. Die Übertretungssanktion müsse entweder betragsmässig oder aber bezüglich der Höhe der alternativen Sanktion der gemeinnützigen Arbeit in der oberen Hälfte des gesetzlichen Strafrahmens ausgefällt werden. Die Überlegungen der Vorinstanz hätten zur Konsequenz, dass bei Straftätern, die in so günstigen finanziellen Verhältnissen lebten, dass für sie analog <ref-law> für die Festsetzung der Ersatzfreiheitsstrafe gemäss <ref-law> ein Umwandlungssatz von mehr als 222 Franken anzuwenden wäre, im Regelfall wegen der gesetzlichen Obergrenze von Fr. 10'000.-- gar keine verschuldensadäquate Busse ausgefällt werden könnte, oder aber, dass es unter Berücksichtigung der Obergrenze bei Bussen für bessersituierte Täter gar nie zu einem Strafregistereintrag kommen könnte (Beschwerde, S. 4 f. Ziff. 3 und 4).
4. 4.1 Die Vorschriften von <ref-law> zum Strafregister entsprechen - abgesehen von den durch das neue Sanktionensystem bedingten Änderungen - den Bestimmungen von Art. 359 ff. aStGB, wie es bis zum 31. Dezember 2006 gültig war. Auch die "Verordnung über das automatisierte Strafregister" vom 1. Dezember 1999 wurde durch die VOSTRA-Verordnung weitergeführt. Ein wesentlicher Unterschied ergibt sich durch den Wegfall der Haftstrafe für die Eintragung von Übertretungssanktionen. Dem Zweck und dem Inhalt des Strafregisters sowie der betreffenden Verordnung liegen aber nach wie vor die gleichen Überlegungen zugrunde.
4.2 Die Abschaffung der Haft als kurze Freiheitsstrafe hat nicht zu einem Verzicht auf die Eintragung von Übertretungssanktionen in VOSTRA geführt. Für den Wegfall der Haft als Eintragungsvoraussetzung musste indessen ein angemessenes Äquivalent gefunden werden. Ein solches existiert letztlich nicht, da nach altem Recht eine Eintragung schon ab 1 Tag Haft erfolgte und man daher nicht einfach auf den alten Umwandlungssatz abstellen konnte (PATRICK GRUBER, Basler Kommentar, StGB II, 2. Aufl., 2007, Art. 366 N. 27). Mit der Festsetzung der Eintragungspflicht bei Bussen über Fr. 5'000.-- und gemeinnütziger Arbeit über 180 Stunden erfolgt die Eintragung von Übertretungen in VOSTRA bei 50% des jeweiligen Strafmaximums (vgl. Art. 106 Abs. 1 und Art. 107 Abs. 1 StGB). Die Grenze von Fr. 5'000.-- bildet gleichzeitig die Limite für die vereinfachte Zumessung der Busse nach Art. 8 Verwaltungsstrafrecht. Sie ist klar höher als die Obergrenze der Ordnungsbussen im Strassenverkehr von Fr. 300.--. Da die gemeinnützige Arbeit im neuen Sanktionensystem nicht mehr nur eine Vollzugsform der Freiheitsstrafe darstellt, sondern als eigenständige Sanktion ausgestaltet ist, war auch die Festlegung einer bestimmten Mindesthöhe bei Verurteilungen zu gemeinnütziger Arbeit zwingend notwendig (GRUBER, a.a.O., Art. 366 N. 29). Die mit der neuen Bemessungsregel verbundenen Nachteile müssen im Interesse einer schlanken Regelung in Kauf genommen werden (GRUBER, a.a.O., Art. 366 N. 30 - 34). Das gilt insbesondere für die Schlechterstellung reicher Täter, da bei diesen die Bussen bei gleichem Verschulden in der Regel höher ausfallen als bei armen Delinquenten. Diese Konsequenz liesse sich nur verhindern, wenn man auch bei Übertretungen die Strafen nach dem Tagessatzsystem berechnen würde. Dann könnte man als Eintragungsvoraussetzung auf eine bestimmte Anzahl Tagessätze abstellen (GRUBER, a.a.O., Art. 366 N. 33). Wie die Beschwerdeführerin zu Recht geltend macht, ist aber die Busse gemäss <ref-law> eine Geldsummensanktion.
4.3 Die Vorinstanz stellt für die Eintragung in VOSTRA nicht auf die Bussensumme, sondern auf die Ersatzfreiheitsstrafe und die ihr äquivalente gemeinnützige Arbeit ab. Damit verletzt sie Bundesrecht.
Die Ersatzfreiheitsstrafe ist aus verschiedenen Gründen kein taugliches Eintragungskriterium. Vorab kann weder dem Wortlaut noch der Entstehungsgeschichte der VOSTRA-Verordnung irgendein Anhaltspunkt entnommen werden, dass die Ersatzfreiheitsstrafe, welche ja nur bei Nichtbezahlung der Busse zum Tragen kommt, für die Eintragung ausschlaggebend sein könnte. Abgesehen von den Schwierigkeiten bei der Berechnung der Ersatzfreiheitsstrafe anstelle der Busse (vgl. zu dieser Problematik STEFAN HEIMGARTNER, Basler Kommentar, StGB I, 2. Aufl., 2007, Art. 106 N. 8 ff.), ist nicht ersichtlich, wo die Grenze zu ziehen wäre, das heisst ab welcher Anzahl Tage Ersatzfreiheitsstrafe der Eintrag erfolgen sollte. Für den von der Vorinstanz vorgenommenen Beizug der oberen Grenze für die gemeinnützige Arbeit mit der Umrechnung gemäss <ref-law> sind wiederum keine Argumente ersichtlich. Von Bedeutung ist schliesslich der Umstand, dass im Nebenstrafrecht die Bussen von Verwaltungsbehörden ausgesprochen werden. Diese können indessen keine Ersatzfreiheitsstrafe verhängen. Wohl entscheidet gemäss <ref-law> über die Ersatzfreiheitsstrafe das Gericht, wenn eine Geldstrafe durch eine Verwaltungsbehörde ausgesprochen wurde. Die Freiheitsstrafe tritt aber nur an die Stelle der Geldstrafe, soweit der Verurteilte diese nicht bezahlt und sie auf dem Betreibungsweg uneinbringlich ist (<ref-law>). Selbst wenn man diese Bestimmung in Anwendung von <ref-law> auf die Bussen anwenden wollte, müsste vor der Festsetzung der Ersatzfreiheitsstrafe einer Verwaltungsbusse durch den ordentlichen Richter vorerst die Nichtbezahlung respektive die Uneinbringlichkeit des Geldbetrages abgewartet werden. Damit hinge die Eintragung in VOSTRA in der Schwebe. Bezahlt aber der Verurteilte die durch eine Verwaltungsbehörde verhängte Busse, so könnte diese - folgt man den Erwägungen der Vorinstanz - auch bei einem Höchstbetrag (z.B. Fr. 500'000.-- nach Art. 56 Spielbankengesetz, SR 935.52) nicht eingetragen werden.
4.4 Die Ausführungen des Bundesgerichtes im Entscheid 134 IV 60 E. 7.3.3, auf welche sich die Vorinstanz stützt (angefochtener Entscheid, E. 6.4.2) helfen bei der Suche nach einem geeigneten Kriterium für die Eintragung der Busse in VOSTRA nicht weiter. Es bleibt bei der Problematik, dass der Bussenbetrag die Komponenten des Verschuldens und der wirtschaftlichen Leistungsfähigkeit nicht aufschlüsselt. Die im Gesamtsummensystem gebildete Busse erschwert die Quantifizierung des Verschuldens. Zudem steht dem Gericht bei der Bemessung der Ersatzfreiheitsstrafe ein weiter Ermessensspielraum zu. Schliesslich löst die Tatsache, dass die Ersatzfreiheitsstrafe gemäss <ref-law> gleichzeitig mit der Busse auszusprechen ist, wie aufgezeigt, das Problem beim Vorliegen einer durch eine Verwaltungsbehörde gefällten Busse gerade nicht.
4.5 Nur wenn sowohl die Bussensumme als auch die Anzahl Stunden gemeinnütziger Arbeit die in der VOSTRA-Verordnung enthaltenen Obergrenzen überschreiten, ist nach Auffassung der Vorinstanz die Gleichbehandlung im Sinne von <ref-law> des Angeklagten, der über ein ausserordentlich hohes Einkommen verfügt, dem aber nur ein geringes Verschulden vorzuwerfen ist, mit einem Angeklagten mit geringem oder durchschnittlichen Einkommen gewährleistet (angefochtener Entscheid, S. 14 E. 6.4.5). Eine gewisse Ungleichbehandlung bei der Eintragung ist angesichts der gesetzlichen Regelung in der Tat nicht zu umgehen. Da aber nicht allein die Busse, sondern auch die im Urteil durch das Gericht verhängte Ersatzfreiheitsstrafe in VOSTRA eingetragen wird, ist die Verschuldenskomponente für die Behörde, welche in einem späteren Verfahren den Registerauszug verlangt, - wie gerade der vorliegende Fall zeigt - nachvollziehbar. Für Strafregisterauszüge zu Handen von Privatpersonen stellt sich die Problematik ohnehin nicht, weil Urteile wegen Übertretungen im Auszug nicht erscheinen, ausser wenn ein Berufsverbot nach Art. 67 verhängt wurde (<ref-law>). Davon, dass die VOSTRA-Verordnung die hier beurteilte Situation nicht erfasst, mithin eine echte Gesetzeslücke vorliegt, kann entgegen der Auffassung des Beschwerdegegners keine Rede sein.
5. Zusammenfassend steht fest, dass massgebliches Kriterium für die Eintragung in VOSTRA gemäss dem Gesetzestext von Art. 3 Abs. 1 lit. c VOSTRA entweder ein Bussenbetrag von mehr als 5'000 Franken oder die Dauer einer gemeinnützigen Arbeit von mehr als 180 Stunden ist. Der angefochtene Entscheid ist deshalb im umstrittenen Punkt in Gutheissung der Beschwerde aufzuheben.
6. Es rechtfertigt sich, vorliegend im Sinne von <ref-law> in der Sache selbst zu entscheiden. Die von der Vorinstanz vorgenommene Ergänzung des Urteils des Gerichtspräsidiums Lenzburg vom 21. Mai 2008, welche lautet: "5. Auf die Mitteilung an das VOSTRA nach Eintritt der Rechtskraft des Urteils wird verzichtet" ist zu streichen.
7. Bei diesem Ausgang des Verfahrens sind die Gerichtskosten dem unterliegenden Beschwerdegegner zu überbinden (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird gutgeheissen.
2. Die in Ziff. 1.1 des Urteils des Obergerichts des Kantons Aargau vom 3. Dezember 2008 angeordnete Ergänzung des erstinstanzlichen Urteils: "5. Auf die Mitteilung an das VOSTRA nach Eintritt der Rechtskraft des Urteils wird verzichtet." wird gestrichen.
3. Die Gerichtskosten von Fr. 2'000.-- werden dem Beschwerdegegner auferlegt.
4. Dieses Urteil wird den Parteien und dem Obergericht des Kantons Aargau, Strafgericht, 3. Kammer, schriftlich mitgeteilt.
Lausanne, 31. März 2009
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Die Gerichtsschreiberin:
Favre Arquint Hill