Sachverhalt:
A. Das Bezirksgericht Baden sprach X._ am 29. April 2009 der groben Verkehrsregelverletzung durch Rechtsüberholen auf der Autobahn schuldig. Es verurteilte ihn zu einer bedingten Geldstrafe von 10 Tagessätzen zu Fr. 70.-- und zu einer Busse von Fr. 300.--. Die von X._ erhobene Berufung wies das Obergericht des Kantons Aargau mit Urteil vom 24. September 2009 ab.
B. Gegen dieses Urteil wendet sich X._ mit Beschwerde in Strafsachen. Er beantragt, er sei vom Vorwurf des Rechtsüberholens auf der Autobahn freizusprechen. Eventualiter sei er der einfachen Verkehrsregelverletzung nach <ref-law> schuldig zu sprechen. Subeventualiter sei das angefochtene Urteil aufzuheben und die Sache zur Neubeurteilung an das Obergericht zurückzuweisen.

Erwägungen:
1. Der Beschwerdeführer rügt zusammengefasst, die Vorinstanz stelle den Sachverhalt in willkürlicher Weise fest und verstosse gegen <ref-law>. Weder das Einvernahmeprotokoll noch der Polizeirapport würden den Sachverhalt mit der erforderlichen Genauigkeit wiedergeben. Der Sachverhalt sei nicht rechtsgenüglich abgeklärt. Bei objektiver Berücksichtigung sämtlicher Umstände drängten sich erhebliche Zweifel auf, weshalb er nach dem Grundsatz in dubio pro reo freizusprechen sei.
1.1 Der Beschwerdeführer macht geltend, der Polizeibeamte A._ sei im Einvernahmeprotokoll davon ausgegangen, dass er 100 km/h gefahren sei. Die Geschwindigkeit des Polizeifahrzeugs und des Citroën hätten 110 km/h betragen. Dem widersprächen die Angaben im Polizeirapport von ca. 100 km/h bei allen Fahrzeugen. Zudem sei das ihm zur Last gelegte Überholmanöver rein rechnerisch nicht möglich, wenn man von den Distanzangaben (Abstand der Fahrzeuge, Ort des Überholmanövers) und Geschwindigkeiten des Einvernahmeprotokolls und des Polizeirapports ausgehe. Die vom Zeugen A._ angefertigte Skizze gebe auch lediglich den Bewegungsablauf seines Fahrzeugs wieder. Die anderen beiden Fahrzeuge seien statisch eingezeichnet. Zudem stehe der vom Obergericht festgestellte Zeitpunkt der Beschleunigung im Widerspruch zum Einvernahmeprotokoll. Das Fahrmanöver habe sich nicht so zugetragen, wie es eingezeichnet sei. Die Skizze enthalte weder die Sperrfläche bei km 92.000 noch die Sicherheitslinie und deren Ende bei km 92.550. Im Übrigen sei es fraglich, wie der Zeuge A._, der sich auf den Strassenverkehr habe konzentrieren müssen, in der Dunkelheit Wahrnehmungen hinsichtlich des hinter ihm fahrenden Verkehrs habe machen können.
Bei seinen Aussagen handle es sich entgegen der Auffassung der Vorinstanz nicht um Schutzbehauptungen. Die Situation am 8. Dezember 2008 sei ihm höchst unangenehm gewesen und er habe eine Auseinandersetzung vor Ort vermeiden wollen.
1.2 Die Vorinstanz geht davon aus, dass der Beschwerdeführer am 8. Dezember 2008 um 5.35 Uhr auf der Autobahn A1 in Richtung Zürich bei km 92.800 das Fahrzeug Citroën rechts überholte. Er sei kurz vor km 92.800 hinter dem Citroën gefahren, habe unter Missachtung der zulässigen Höchstgeschwindigkeit (was ihm nicht zur Last gelegt werde) beschleunigt, diesen rechts passiert und sei vor ihm auf den Mittelstreifen gewechselt (angefochtenes Urteil S. 9). Sie stützt sich auf das Einvernahmeprotokoll, die Skizze und den Polizeirapport, die Aussagen des Beschwerdeführers nach seiner Anhaltung sowie die Zeugenaussagen des Polizeibeamten A._. Der Beschwerdeführer habe den im Einvernahmeprotokoll umschriebenen Sachverhalt sowie die darin enthaltene Skizze anlässlich der Anhaltung unterschriftlich anerkannt (angefochtenes Urteil S. 6). Der Zeuge A._ habe das Rechtsüberholen des Beschwerdeführers vor erster Instanz bestätigt und dieselben Angaben seien im Polizeirapport und Einvernahmeprotokoll enthalten.
Es gebe keine Hinweise, dass sich der Beschwerdeführer beim Zusammentreffen der A1 mit der A3 auf gleicher Höhe befunden habe, wie der Citroën und das zivile Polizeiauto. Ebensowenig sei die Rede davon, dass alle drei Fahrzeuge über einen Kilometer nebeneinander gefahren seien, bis auf dem Mittelstreifen ein viertes langsameres Auto sichtbar geworden sei, und der Beschwerdeführer erst dann rechts am Citroën vorbeigefahren sei. Diese Version des Beschwerdeführers sei als Schutzbehauptung zu werten (angefochtenes Urteil S. 8 f.).
Die zur A1 hinzukommende dritte Fahrspur sei keine Einspurstrecke und am Tatort auch nicht als solche signalisiert (angefochtenes Urteil S. 9 mit Hinweis auf die Fotodokumentation act. 26 ff.).
1.3 Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat (<ref-law>). Feststellungen zum Sachverhalt prüft es nur unter dem Gesichtspunkt der Willkür (<ref-law>). Es hat die Voraussetzungen an die Begründungspflicht einer Willkürrüge und wann Willkür vorliegt, bereits mehrfach dargelegt. Darauf kann verwiesen werden (<ref-ruling> E. 2.1 und 2.2 S. 245 f.; <ref-ruling> E. 1.2 S. 177; je mit Hinweisen).
1.4 Die Vorbringen des Beschwerdeführers sind nicht geeignet, Willkür darzutun. Die Beweiswürdigung der Vorinstanz, welche sich auf das nach der Anhaltung erstellte Einvernahmeprotokoll inklusive der Skizze, die darin enthaltene Bestätigung des Beschwerdeführers zum Sachverhalt, den Polizeirapport und die Zeugenaussagen des Polizeibeamten A._ stützt, ist nachvollziehbar und schlüssig begründet. Dass die Geschwindigkeiten und Distanzen im Einvernahmeprotokoll detaillierter, d.h. bezüglich der einzelnen Fahrspuren, angegeben werden als im Polizeirapport, wo eine ungefähre Schätzung für alle Fahrzeuge vorgenommen wird, ist nicht zu beanstanden. Ebenso ist es nicht geradezu willkürlich, wenn die Vorinstanz davon ausgeht, der Beschwerdeführer habe kurz vor dem Einholen des Citroën beschleunigt, während im Einvernahmeprotokoll das Beschleunigen nach dem Vorbeifahren aber vor dem Einbiegen beschrieben wird. Denn zwischen dem Beschleunigen und Überholen liegt nur ein kurzer Zeitraum und die genaue Reihenfolge vermögen das im Einvernahmeprotokoll festgehaltene Rechtsüberholen nicht in Frage zu stellen. Auch die hypothetischen Berechnungen des Beschwerdeführers lassen den festgestellten Sachverhalt nicht als schlechterdings unhaltbar erscheinen. Entgegen seiner Auffassung ergeben sich aus dem Einvernahmeprotokoll, der Skizze und dem Polizeirapport weder die seinen Berechnungen zugrunde gelegten Distanzen zwischen den Fahrzeugen noch eine konstante Geschwindigkeit seines Fahrzeugs. Ebenso unbehelflich sind die Einwendungen gegen die Skizze. Bei dieser handelt es sich naturgemäss um eine ungefähre Darstellung der örtlichen Verhältnisse, welche weder massstabsgetreu noch mit allen Details versehen ist. Die vom Beschwerdeführer gerügten Punkte ändern nichts am Kerngeschehen, dem Vorgang des Rechtsüberholens bei km 92.800. Dieses wurde vom Beschwerdeführer im Einvernahmeprotokoll zunächst anerkannt und wird vom Zeugen A._ mehrfach (Einvernahmeprotokoll, Polizeirapport, Zeugenaussage) bestätigt. Insgesamt durfte die Vorinstanz willkürfrei und ohne Verletzung des Grundsatzes in dubio pro reo davon ausgehen, dass sich der Sachverhalt in der festgestellten Weise zugetragen hat (vgl. E. 1.2).
2. 2.1 Der Beschwerdeführer rügt, die Vorinstanz verletze den Grundsatz des rechtlichen Gehörs, indem sie den Lenker des überholten Personenwagens nicht befragt habe.
2.2 Die Vorinstanz erwägt, der Sachverhalt sei hinreichend abgeklärt. In antizipierter Beweiswürdigung sei auf die Einvernahme des Fahrzeuglenkers des rechts überholten Citroën zu verzichten.
2.3 Der Anspruch auf Befragung von Zeugen ist Teil des rechtlichen Gehörs, welches seine Grundlage im Anspruch auf ein faires Verfahren nach Art. 6 Ziff. 1 EMRK und Art. 29 Abs. 1 und 2 BV hat (<ref-ruling> E. 5.2 S. 147). Er ist nicht verletzt, wenn der Richter nur jene Beweisbegehren berücksichtigt, die nach seiner Würdigung entscheiderheblich sind (<ref-ruling> E. 3.1 S. 154 mit Hinweis), bzw. in antizipierter Beweiswürdigung weitere Beweisanträge ablehnt (<ref-ruling> E. 5.3 S. 148 mit Hinweisen).
2.4 Entgegen der Auffassung des Beschwerdeführers verletzt die Vorinstanz den Anspruch auf rechtliches Gehör nicht. Bei der gegebenen Sachlage, bei welcher der Polizist A._ das Kerngeschehen mehrmals identisch schilderte und der Beschwerdeführer dieses anlässlich der ersten Einvernahme vor Ort bestätigte, durfte die Vorinstanz auf den beantragten Zeugen verzichten.
3.1 3.1.1 Der Beschwerdeführer macht geltend, die rechtliche Würdigung des Sachverhaltes durch die Vorinstanz verstosse gegen Bundesrecht. Das Rechtsvorbeifahren an Fahrzeugen sei nach Art. 36 Abs. 5 VRV erlaubt, solange die Spuren durch eine Sicherheitslinie getrennt seien. Er sei auf gleicher Höhe wie das Fahrzeug Citroën gefahren. Es handle sich nicht um ein langsamer vorausfahrendes Fahrzeug. Deshalb sei der Tatbestand des Rechtsüberholens auf der Autobahn nicht erfüllt.
3.1.2 Nach <ref-law> ist links zu überholen, woraus ein Verbot des Rechtsüberholens folgt. Ein Überholen liegt vor, wenn ein schnelleres Fahrzeug ein in gleicher Richtung langsamer vorausfahrendes einholt, an ihm vorbeifährt und vor ihm die Fahrt fortsetzt, wobei weder das Ausschwenken noch das Wiedereinbiegen eine notwendige Voraussetzung des Überholens bildet (<ref-ruling> E. 2a S. 195). Eine Ausnahme vom Verbot des Rechtsüberholens sieht Art. 8 Abs. 3 Satz 1 der Verkehrsregelverordnung vom 13. November 1962 (VRV; SR 741.11) allgemein und Art. 36 Abs. 5 lit. a VRV besonders auf Autobahnen "beim Fahren in parallelen Kolonnen" vor, jedoch lediglich in der Weise, dass bloss das Rechtsvorbeifahren an anderen Fahrzeugen gestattet ist. Auf Autobahnen ist zudem das Rechtsvorbeifahren an anderen Fahrzeugen auf Einspurstrecken gestattet, sofern für die einzelnen Fahrstreifen unterschiedliche Fahrziele signalisiert sind (Art. 36 Abs. 5 lit. b VRV) sowie auf dem Beschleunigungsstreifen von Einfahrten bis zum Ende der Doppellinien-Markierung (lit. c) und auf dem Verzögerungsstreifen (lit. d).
3.1.3 Soweit der Beschwerdeführer bei seiner rechtlichen Würdigung von einem anderen Sachverhalt ausgeht als die Vorinstanz (z.B. längeres Nebeneinanderfahren mit dem Citroën, Ort des Überholmanövers), ist darauf nicht mehr einzugehen. Diese Rügen wurden bereits geprüft (vgl. E. 1). Das Überholmanöver ereignete sich nach den Feststellungen der Vorinstanz bei km 92.800 (angefochtenes Urteil S. 9), wo die Fahrspur der A3 nicht mehr durch eine Sicherheitslinie abgegrenzt ist und keine Einspurstrecke besteht (vgl. angefochtenes Urteil S. 9 mit Hinweis auf die Fotodokumentation act. 26 ff.). Der Beschwerdeführer näherte sich auf der rechten Spur einer dreispurigen Autobahn von hinten dem auf dem ersten Überholstreifen fahrenden Fahrzeug Citroën, fuhr rechts an diesem vorbei und bog vor ihm auf die erste Überholspur ein (angefochtenes Urteil S. 9). Die Fahrzeuge fuhren nicht in parallelen Kolonnen (angefochtenes Urteil S. 10). Dadurch vollzog er ein Rechtsüberholen auf der Autobahn, welches nach Art. 35 Abs. 1 VRV nicht gestattet ist.
3.1.3 Soweit der Beschwerdeführer bei seiner rechtlichen Würdigung von einem anderen Sachverhalt ausgeht als die Vorinstanz (z.B. längeres Nebeneinanderfahren mit dem Citroën, Ort des Überholmanövers), ist darauf nicht mehr einzugehen. Diese Rügen wurden bereits geprüft (vgl. E. 1). Das Überholmanöver ereignete sich nach den Feststellungen der Vorinstanz bei km 92.800 (angefochtenes Urteil S. 9), wo die Fahrspur der A3 nicht mehr durch eine Sicherheitslinie abgegrenzt ist und keine Einspurstrecke besteht (vgl. angefochtenes Urteil S. 9 mit Hinweis auf die Fotodokumentation act. 26 ff.). Der Beschwerdeführer näherte sich auf der rechten Spur einer dreispurigen Autobahn von hinten dem auf dem ersten Überholstreifen fahrenden Fahrzeug Citroën, fuhr rechts an diesem vorbei und bog vor ihm auf die erste Überholspur ein (angefochtenes Urteil S. 9). Die Fahrzeuge fuhren nicht in parallelen Kolonnen (angefochtenes Urteil S. 10). Dadurch vollzog er ein Rechtsüberholen auf der Autobahn, welches nach Art. 35 Abs. 1 VRV nicht gestattet ist.
3.2 3.2.1 Der Beschwerdeführer macht geltend, es liege keine grobe sondern eine einfache Verkehrsregelverletzung nach <ref-law> vor. Sein Fahrmanöver sei nicht geeignet gewesen, andere Verkehrsteilnehmer zu einer gefährlichen Fehlreaktion zu veranlassen. Er sei längere Zeit neben dem überholten Fahrzeug hergefahren, und habe es nicht überraschend rechts überholt. Das Verkehrsaufkommen sei schwach gewesen und der er habe den Lenker des Citroën weder konkret gefährdet noch behindert. Sein Verhalten sei nicht rücksichtslos, da er ein weiter vorne fahrendes, langsames Fahrzeug habe links überholen wollen.
3.2.2 Der Tatbestand der groben Verletzung von Verkehrsregeln im Sinne von <ref-law> setzt objektiv voraus, dass der Täter eine wichtige Verkehrsvorschrift in objektiv schwerer Weise missachtet und die Verkehrssicherheit ernstlich gefährdet. Eine ernstliche Gefahr für die Sicherheit anderer ist nicht erst bei einer konkreten, sondern bereits bei einer erhöhten abstrakten Gefährdung gegeben. Ob eine konkrete, eine erhöhte abstrakte oder nur eine abstrakte Gefahr geschaffen wird, hängt von der Situation ab, in welcher die Verkehrsregelverletzung begangen wird. Wesentliches Kriterium für die Annahme einer erhöhten abstrakten Gefahr ist die Nähe der Verwirklichung. Die allgemeine Möglichkeit der Verwirklichung einer Gefahr genügt demnach nur zur Erfüllung des Tatbestands von <ref-law>, wenn in Anbetracht der Umstände der Eintritt einer konkreten Gefährdung oder gar einer Verletzung nahe liegt (<ref-ruling> E. 3.2 mit Hinweisen).
Subjektiv erfordert der Tatbestand von <ref-law> ein rücksichtsloses oder sonst schwerwiegend verkehrswidriges Verhalten, d.h. ein schweres Verschulden, bei fahrlässigem Handeln mindestens grobe Fahrlässigkeit. Diese ist immer zu bejahen, wenn der Täter sich der allgemeinen Gefährlichkeit seiner verkehrswidrigen Fahrweise bewusst ist (<ref-ruling> E. 3.2 S. 136 mit Hinweisen).
3.3 Das Verbot des Rechtsüberholens ist eine für die Verkehrssicherheit objektiv wichtige Vorschrift, deren Missachtung eine erhebliche Gefährdung der Verkehrssicherheit mit beträchtlicher Unfallgefahr nach sich zieht und daher objektiv schwer wiegt. Wer auf der Autobahn fährt, muss sich darauf verlassen können, dass er nicht plötzlich rechts überholt wird. Das Rechtsüberholen auf der Autobahn, wo hohe Geschwindigkeiten gefahren werden, stellt eine erhöht abstrakte Gefährdung anderer Verkehrsteilnehmer dar (<ref-ruling> E. 3 S. 196 f.). Dies gilt insbesondere im vorliegenden Fall, wo der Beschwerdeführer das Überholmanöver frühmorgens bei Dunkelheit bzw. eingeschränkten Sichtverhältnissen durchführte. Wie die Vorinstanz zutreffend ausführt, musste er jederzeit damit rechnen, dass der überholte Fahrzeuglenker auf die rechte Spur wechseln wollte, da sich rund ein Kilometer später eine Ausfahrt befindet. Obwohl der Beschwerdeführer wusste, dass er mit einem Rechtsüberholen andere Fahrzeuglenker verunsichern kann, überholte er rechts (angefochtenes Urteil S. 8, 12). Er führte das Manöver nach den vorinstanzlichen Erwägungen vorsätzlich, also auch willentlich aus. Die rechtliche Qualifikation der Tat als grobe Verkehrsregelverletzung durch Rechtsüberholen auf der Autobahn nach <ref-law> i.V.m. Art. 35 Abs. 1 und Art. 23 Abs. 5 VRV erweist sich als bundesrechtskonform.
4. Die Beschwerde ist abzuweisen. Bei diesem Ausgang des Verfahrens hat der Beschwerdeführer die Gerichtskosten zu tragen (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2. Die Gerichtskosten von Fr. 4'000.-- werden dem Beschwerdeführer auferlegt.
3. Dieses Urteil wird den Parteien und dem Obergericht des Kantons Aargau, Strafgericht, 3. Kammer, schriftlich mitgeteilt.
Lausanne, 23. Februar 2010
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Die Gerichtsschreiberin:
Favre Koch