Sachverhalt:
A. Mit Urteil des Strafgerichtspräsidiums vom 27. Februar 2008 wurde X._ in Abänderung des Strafbefehls des Bezirksstatthalteramtes Arlesheim vom 23. April 2007 wegen mehrfacher Widerhandlung gegen die Verordnung vom 19. Juni 1995 über die Arbeits- und Ruhezeit der berufsmässigen Motorfahrzeugführer und -führerinnen (Chauffeurverordnung, ARV 1, SR 822.221) schuldig gesprochen und zu einer Busse von Fr. 4'000.-- verurteilt.
B. Das Kantonsgericht Basel-Landschaft stellte am 15. Dezember 2008 das Verfahren gegen X._ zufolge Eintritts der Verfolgungsverjährung ein.
C. Gegen das Urteil des Kantonsgerichts erhebt die Staatsanwaltschaft des Kantons Basel-Landschaft Beschwerde in Strafsachen. Sie beantragt, X._ sei der mehrfachen Widerhandlung gegen die Chauffeurverordnung schuldig zu sprechen und mit einer Busse von Fr. 4'000.-- zu belegen. Eventualiter sei das Urteil aufzuheben und die Sache an das Kantonsgericht zurückzuweisen.
D. Das Kantonsgericht Basel-Landschaft als auch X._ beantragen die Abweisung der Beschwerde.

Erwägungen:
1. 1.1 Die Vorinstanz vertritt die Auffassung, die zur Anklage gebrachten Delikte seien verjährt. Die Verjährungsfrist für Übertretungen werde in <ref-law> abschliessend geregelt und betrage drei Jahre. Seit den Taten, welche der Beschwerdeführer zwischen dem 4. Juli 2005 und dem 26. August 2005 begangen haben soll, seien mehr als drei Jahre verstrichen. Dabei hemme das erstinstanzliche Urteil den Lauf der Verjährungsfrist nach <ref-law> nicht. <ref-law> finde auf Übertretungen keine Anwendung, sondern beziehe sich in seiner Gesamtheit ausschliesslich auf die Verfolgungsverjährung von Verbrechen und Vergehen. Es sei nicht logisch, dass lediglich ein Absatz einer Gesetzesnorm, nämlich <ref-law>, für Übertretungen gelten soll.
Sinn und Zweck der Verjährungsregeln ergäben dasselbe Resultat. Die Verjährung beruhe auf dem Gedanken, dass der Zeitablauf den Unrechtsausgleich bedeutungslos werden lasse. Mit der Zeit werde es zudem schwieriger, den massgeblichen Sachverhalt zu rekonstruieren. Aus verfahrensökonomischer Sicht sei eine endgültige Verjährung bei Übertretungen, welche sich durch ein geringes Vergeltungsbedürfnis auszeichneten, nach drei Jahren sinnvoll.
Das bis Ende September 2002 geltende alte Verjährungsrecht habe noch zwischen relativer und absoluter Verjährung unterschieden. Damals sei bei Übertretungen die absolute Verjährung in zwei Jahren eingetreten. Die Unterscheidung zwischen relativer und absoluter Verjährung sei abgeschafft und die Verjährungsfrist auf drei Jahre erhöht worden. Zufolge dieser Verlängerung rechtfertige es sich, <ref-law> nicht auf Übertretungen anzuwenden.
1.2 Die Beschwerdeführerin rügt, die Vorinstanz verstosse gegen Bundesrecht. Sie habe zwar korrekterweise das neuere, seit dem 1. Januar 2007 in Kraft stehende Recht als milderes Recht angewendet. Artikel 97 Abs. 3 StGB (bzw. der gleichlautende Art. 70 Abs. 3 aStGB, welcher zur Tatzeit gegolten habe) sei aber entgegen ihrer Auffassung auch auf Übertretungen anwendbar, da <ref-law> auf die Bestimmungen des ersten Teils des Strafgesetzbuches verweise.
Auch der Grundsatz der Verhältnismässigkeit rechtfertige keine andere Lösung. Dem geringen Verschulden werde schon bei der Sanktionsart Rechnung getragen. Zudem sei eine überlange Verfahrensdauer zwischen dem erst- und zweitinstanzlichen Verfahren in der Praxis äusserst selten. Auch die Rekonstruktion des Sachverhalts spiele vor der zweiten Instanz in der Regel eine untergeordnete Rolle.
1.3 Wie die Vorinstanz geht auch der Beschwerdegegner in seiner Vernehmlassung gestützt auf den Wortlaut von <ref-law> davon aus, dass die Strafverfolgung innert drei Jahren definitiv verjährt und <ref-law> auf Übertretungen nicht anzuwenden ist.
2. 2.1 Ist vor Ablauf der Verjährungsfrist ein erstinstanzliches Urteil ergangen, so tritt die Verjährung nicht mehr ein (<ref-law>). Das Bundesgericht hat gestützt auf diese gesetzliche Bestimmung entschieden, dass die Verfolgungsverjährung mit der Fällung des erstinstanzlichen Urteils und nicht erst mit dessen Eröffnung endet (<ref-ruling> E. 2.3 S. 105). Eine Strafverfügung ist dem erstinstanzlichen Urteil gleichgestellt (<ref-ruling> E. 9.4.4 S. 117). Unter erstinstanzlichen Urteilen sind ausschliesslich verurteilende Erkenntnisse zu verstehen (<ref-ruling> E. 2.1 S. 331).
2.2 Nach der Botschaft zur Änderung des Schweizerischen Strafgesetzbuches vom 21. September 1998 (BBl 1999 1979 ff. Ziff. 216.11) war ein Hauptproblem des damals geltenden Rechts, dass die absolute Verfolgungsverjährung noch im Rechtsmittelverfahren eintreten konnte. Dieses wurde dadurch behoben, dass nach den neuen Bestimmungen die Strafverfolgungsverjährung endet, sobald ein erstinstanzliches Urteil ergangen ist. Als erstinstanzliches Urteil gilt sowohl ein Urteil im Abwesenheitsverfahren als auch ein Strafmandat (Strafbefehl), das weder Gegenstand einer Einsprache noch eines Rechtsmittelverfahrens war. Gegenüber der Gefahr, dass dem Rechtsmittelverfahren keine Grenzen mehr gesetzt sind, bleibt dem Angeschuldigten der Schutz durch das Verzögerungsverbot nach <ref-law> sowie das Beschleunigungsgebot nach Art. 6 EMRK (BBl 1999 2134 Ziff. 216.11). Gleichzeitig wurden das Ruhen und die Unterbrechung der Verjährungsfristen - und damit der Unterschied zwischen relativer und absoluter Verjährungsfrist - abgeschafft und die Verjährungsfristen verlängert (BBl 1999, a.a.O.).
2.3 Die Strafverfolgung und die Strafe für Übertretungen verjähren in drei Jahren (<ref-law>). Hingegen sind weder Beginn noch Ende der Verjährungsfrist in <ref-law> geregelt. Aufgrund von <ref-law> gelten die Bestimmungen des Ersten Teils des Strafgesetzbuches - d.h. unter anderem auch <ref-law> - grundsätzlich auch für Übertretungen, soweit in den Art. 103 bis <ref-law> nichts Abweichendes geregelt ist. <ref-law> verweist generell und ausnahmslos auf den ersten Teil des Strafgesetzbuches, soweit im Übertretungsstrafrecht keine speziellen Regeln aufgestellt werden. Weder dem Gesetz noch der Botschaft lässt sich entnehmen, dass einzelne Absätze der Gesetzesbestimmungen des ersten Teils auf das Übertretungsstrafrecht keine Anwendung finden sollen. Die Botschaft hält im Gegenteil ausdrücklich fest, dass die Verfolgungsverjährung auch im Strafbefehlsverfahren, also bei geringfügigeren Delikten, mit dem erstinstanzlichen Urteil endet (BBl 1999, a.a.O.). Gestützt auf den Willen des Gesetzgebers soll die Verfolgungsverjährung im Rechtsmittelverfahren grundsätzlich nicht mehr eintreten (a.a.O.).
2.4 In einem nicht publizierten Entscheid hat das Bundesgericht aArt. 70 Abs. 3 StGB, welcher dem neuen <ref-law> entspricht, auf Übertretungen angewendet (vgl. Urteil 6P.182/2004 vom 2. Mai 2005 E. 3.3).
2.5 Auch die Lehre spricht sich, soweit ersichtlich, für die Anwendbarkeit von <ref-law> auf Übertretungen aus (PETER MÜLLER, in: Basler Kommentar, Strafrecht I, 2. Aufl. 2007, N. 70 vor <ref-law>; STEFAN HEIMGARTNER, in: Basler Kommentar, Strafrecht I, 2. Aufl. 2007, N. 13 zu <ref-law>; STEFAN TRECHSEL/BRUNO STÖCKLI, in: Schweizerisches Strafgesetzbuch, Praxiskommentar, 1. Aufl. 2008, N. 1 zu <ref-law>; MARTIN SCHUBARTH, Das neue Recht der strafrechtlichen Verjährung, Schweizerische Zeitschrift für Strafrecht (ZStrR) 2002 S. 331 Ziff. 24). DENYS präzisiert zu aArt. 70 Abs. 3 StGB, dass die Entscheidung einer Administrativbehörde, z.B. in einem Ordnungsbussenverfahren, nicht unter den Begriff "erstinstanzliches Urteil" falle. Erst der Entscheid einer gerichtlichen Behörde, welche die Entscheidung der Administrativbehörde im Rechtsmittelverfahren überprüft, erachtet dieser Autor als erstinstanzliches Urteil im Sinne von aArt. 70 Abs. 3 StGB (CHRISTIAN DENYS, Prescription de l'action pénale: les nouveaux Art. 70, 71, 109 et 333 al. 5 CP, la semaine judiciaire 2003, vol. II, S. 59 f.).
2.6 Strafverfügungen ergehen gestützt auf die in den jeweiligen kantonalen Prozessordnungen festgelegten Kompetenzaufteilungen bei nicht allzu schwerwiegenden Delikten. Das Strafbefehlsverfahren ist nach dem Entwurf zur Schweizerischen Strafprozessordnung insbesondere auf Übertretungen anwendbar, d.h. in Fällen, in welchen lediglich die Busse als Strafe zur Verfügung steht (<ref-law>; BBl 2006 1389, Art. 355 StPO/CH; PETER GOLDSCHMID/THOMAS MAURER/JÜRG SOLLBERGER, Kommentierte Textausgabe zur Schweizerischen Strafprozessordnung, 1. Aufl. 2008, S. 344 ff.). Werden Strafverfügungen und Strafbefehle generell als erstinstanzliche Urteile im Sinne von <ref-law> qualifiziert, soweit sie in Rechtskraft erwachsen, so ist diese Bestimmung auch auf Übertretungen anzuwenden. Aus der Botschaft ergibt sich dasselbe Resultat. Darin findet sich kein Hinweis, dass der Gesetzgeber Verbrechen bzw. Vergehen und Übertretungen bei der Verfolgungsverjährung nach einem erstinstanzlichen Urteil anders behandeln wollte.
Die Auffassung der Vorinstanz, <ref-law> sei auf Übertretungen nicht anwendbar, ist unzutreffend und verletzt Bundesrecht.
3. Die Beschwerde ist gutzuheissen, das angefochtene Urteil aufzuheben und die Sache zur neuen Entscheidung an die Vorinstanz zurückzuweisen. Die Gerichtskosten sind dem Beschwerdegegner als unterliegende Partei aufzuerlegen (<ref-law>). Eine Parteientschädigung ist keine zuzusprechen (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird gutgeheissen, das Urteil des Kantonsgerichts Basel-Landschaft vom 15. Dezember 2008 aufgehoben und die Sache zur neuen Entscheidung an die Vorinstanz zurückgewiesen.
2. Die Gerichtskosten von Fr. 2'000.-- werden dem Beschwerdegegner auferlegt.
3. Dieses Urteil wird den Parteien und dem Kantonsgericht Basel-Landschaft, Abteilung Zivil- und Strafrecht, schriftlich mitgeteilt.
Lausanne, 16. Juli 2009
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Die Gerichtsschreiberin:
Favre Koch