Faits:
A. A._ a été interpellé le 1er février 2010 dans le canton de Saint-Gall alors qu'il s'apprêtait à passer la frontière autrichienne au volant d'une voiture volée. Il a été interrogé par la police cantonale et par le Juge d'instruction du canton de Saint-Gall avant d'être transféré dans le canton de Genève. Le 3 février 2010, il a été auditionné par la police judiciaire genevoise et le lendemain il a été entendu par le Juge d'instruction du canton de Genève, qui a décerné un mandat d'arrêt à son encontre. Il a été inculpé de vol pour avoir, à Genève, dans la nuit du 30 au 31 janvier 2010, dérobé un véhicule LEXUS LS 600 h d'une valeur de 140'000 fr. stationné devant le garage Emil Frey. Sa détention a été prolongée une première fois le 12 février 2010 pour une durée d'un mois.
Le 11 mars 2010, le Procureur général du canton de Genève a requis la prolongation de la détention du prévenu pour une durée de trois mois.
Par ordonnance du 12 mars 2010, la Chambre d'accusation du canton de Genève (ci-après: la Chambre d'accusation) a accordé la prolongation sollicitée jusqu'au 12 avril 2010.
B. Agissant par la voie du recours en matière pénale, A._ demande au Tribunal fédéral de déclarer nulle l'ordonnance de la Chambre d'accusation du 12 mars 2010, d'ordonner sa mise en liberté ainsi que le retrait du dossier de tous les procès-verbaux établis depuis le 1er janvier 2010 par les différentes autorités qui l'ont interrogé et de constater la nullité du mandat d'arrêt décerné le 4 mars 2010. A titre subsidiaire, il conclut à l'annulation de l'ordonnance attaquée et, plus subsidiairement, au renvoi de la cause à l'autorité précédente pour nouvelle décision dans le sens des considérants. Il requiert en outre l'effet suspensif, sa mise en liberté immédiate jusqu'à droit jugé au fond et l'assistance judiciaire. Il se plaint pour l'essentiel d'une violation de l'art. 6 CEDH, invoquant un droit à "l'avocat de la première heure".
La Chambre d'accusation se réfère aux considérants de sa décision. Le Procureur général s'en rapporte à justice quant à la recevabilité du recours et, sur le fond, fait siens les motifs invoqués par la Chambre d'accusation. Le recourant a indiqué, le 1er avril 2010, qu'il renonçait à répliquer.
Par ordonnance du 7 avril 2010, la Chambre d'accusation a prolongé une nouvelle fois la détention du recourant jusqu'au 17 juin 2010.

Considérant en droit:
1. 1.1 La décision attaquée, qui ordonne la prolongation de la détention préventive du recourant pour une durée d'un mois, peut faire l'objet d'un recours en matière pénale au sens des <ref-law>. Formé en temps utile (<ref-law>) contre une décision prise en dernière instance cantonale (<ref-law>) et qui touche le recourant dans ses intérêts juridiquement protégés (art. 81 al. 1 let. a et b ch. 1 LTF), le recours est recevable.
1.2 Bien que la détention du recourant repose à l'heure actuelle sur l'ordonnance du 7 avril 2010, celui-ci conserve un intérêt pratique et actuel au maintien de son recours contre l'ordonnance du 12 mars 2010, puisqu'il conteste pour l'essentiel la validité du mandat d'arrêt décerné le 4 mars 2010 et fait valoir que la violation de son droit à un "avocat de la première heure" devrait entraîner sa libération immédiate.
2. Dans l'ordonnance attaquée, la Chambre d'accusation a constaté que la procédure dirigée contre le recourant n'était pas terminée et que les conditions posées à la délivrance du mandat d'arrêt existaient toujours. Par ailleurs, même si la Cour européenne des droits de l'homme avait admis un droit à un avocat dès la première heure, elle n'en avait toutefois pas déduit que la mise en détention avait été illégale. En vertu de l'art. 23 de la Constitution genevoise, le droit à un avocat devait être garanti à l'inculpé au stade de sa première comparution devant le Juge d'instruction, ce qui avait été le cas en l'espèce. Le mandat d'arrêt n'était donc pas entaché de nullité et aucune pièce du dossier ne devait être écartée de la procédure.
Le recourant ne remet pas en cause les motifs de la détention. En revanche, il fait valoir que l'art. 6 par. 3 let. c CEDH garantit le droit à un avocat dès le premier interrogatoire de police. Or, la police genevoise a refusé de lui accorder l'assistance d'un avocat au motif que l'art. 107A du code de procédure pénale cantonal genevois (ci-après: CPP/GE) ne le permettait pas. A Saint-Gall, alors qu'il avait exprimé sa volonté d'être assisté par un avocat, les interrogatoires et auditions s'étaient également déroulés en l'absence d'un défenseur. Cette violation devait avoir pour conséquence que les procès-verbaux établis sans la présence d'un avocat sont écartés de la procédure. De même, sa détention reposait sur un mandat d'arrestation vicié, ce qui entraînait sa libération immédiate.
3. 3.1 Selon l'art. 23 let. a de la Constitution genevoise, tout inculpé doit, au début de la première comparution devant le juge d'instruction, être expressément informé de son droit de se faire assister par un défenseur. L'<ref-law>/GE précise que l'inculpé a le droit d'obtenir la visite d'un avocat et de conférer librement avec lui, dès la fin de son interrogatoire par l'officier de police, mais au plus tard à la première heure ouvrable à l'issue des 24 heures suivant le début de son audition par la police. A l'instar de la plupart des autres cantons, le droit cantonal genevois n'autorise pas le défenseur à être présent dès le stade des interrogatoires du prévenu par la police, dans le cadre de la procédure d'investigation.
Cette situation changera avec l'entrée en vigueur, le 1er janvier 2011, du Code de procédure pénale suisse (CPP; FF 2007 6583), qui consacre le droit à un "avocat de la première heure". Aux termes de l'art. 158 al. 1 let. c CPP, au début de la première audition, la police ou le ministère public informent le prévenu dans une langue qu'il comprend qu'il a le droit de faire appel à un défenseur ou de demander un défenseur d'office. Les auditions effectuées sans que ces informations aient été données ne seront pas exploitables (<ref-law>). A l'heure actuelle toutefois, aucune disposition de droit fédéral ne garantit un droit à l'avocat de la première heure.
Le recourant ne reproche pas à la Chambre d'accusation d'avoir mal appliqué le droit cantonal ou fédéral. Il estime cependant qu'en refusant de constater que son droit à un avocat de la première heure n'avait pas été respecté, la Chambre d'accusation a violé l'art. 6 CEDH et sa mise en détention serait de ce fait illégale.
3.2 En vertu de l'art. 6 par. 3 let. c CEDH, tout accusé a notamment droit à se défendre lui-même ou avoir l'assistance d'un défenseur de son choix. Cette garantie constitue un aspect particulier du droit au procès équitable au sens de l'art. 6 par. 1 CEDH. Selon la jurisprudence récente de la Cour européenne des droits de l'homme, cette disposition confère à l'accusé le droit de bénéficier de l'assistance d'un avocat dès les premiers stades des interrogatoires de police, sauf à démontrer, à la lumière des circonstances particulières de l'espèce, qu'il existe des raisons impérieuses de restreindre ce droit. Même dans ce dernier cas, pareille restriction - quelle que soit sa justification - ne doit pas indûment préjudicier aux droits découlant pour l'accusé de l'art. 6 CEDH; il est en principe porté une atteinte irrémédiable aux droits de la défense lorsque des déclarations incriminantes faites lors d'un interrogatoire de police subi sans assistance possible d'un avocat sont utilisées pour fonder une condamnation (arrêt de la Cour européenne des droits de l'homme Salduz c. Turquie du 27 novembre 2008 par. 50 ss). Dans l'affaire Salduz c. Turquie, la Cour européenne des droits de l'homme a constaté une violation de l'art. 6 par. 3 let. c CEDH, le droit du requérant à bénéficier de l'assistance d'un avocat ayant été restreint pendant sa garde à vue. Ni l'assistance fournie ultérieurement par un avocat ni la nature contradictoire de la suite de la procédure n'avaient pu porter remède à cette atteinte. Il n'appartenait toutefois pas à la Cour de spéculer sur l'impact qu'aurait eu sur l'aboutissement de la procédure la possibilité pour le requérant de se faire assister par un avocat dès son arrestation (arrêt précité Salduz c. Turquie, par. 58). La forme la plus appropriée de redressement était, pourvu que le requérant le demande, un nouveau procès conforme aux exigences de l'art. 6 par. 1 CEDH.
Jusqu'à présent, le Tribunal fédéral s'est refusé à inférer directement de l'art. 6 par. 3 CEDH un droit pour le prévenu de communiquer librement avec son défenseur immédiatement après son arrestation (<ref-ruling>; arrêt 1P.556/2006 du 25 janvier 2007; arrêt 6B_700/2009 du 26 novembre 2009). La question de savoir si ce point devrait actuellement être résolu différemment peut rester indécise en l'espèce, puisque le constat d'une éventuelle violation de l'art. 6 CEDH ne permettrait de toute façon pas d'arriver à une solution différente de celle retenue par la Chambre d'accusation.
4. Dans le cas particulier, il apparaît que le recourant n'a pas eu la possibilité d'être assisté d'un défenseur lors de ses premiers interrogatoires devant la police, que ce soit dans le canton de Saint-Gall ou à Genève, alors qu'il en avait expressément fait la demande. Lors de ces auditions, il a fait des aveux, reconnaissant être l'auteur du vol reproché. Il a confirmé ses déclarations devant le Juge d'instruction du canton de Genève, auquel il a indiqué ne pas avoir besoin d'un avocat pour l'instant. Dans la mesure où un droit à un avocat de la première heure devrait être reconnu au recourant, il apparaît que celui-ci n'a pas été respecté.
4.1 Le constat de cette violation n'a cependant pas pour conséquence, comme le soutient le recourant, que le mandat d'arrêt décerné à son encontre, de même que sa détention, ne serait pas valide. En effet, si une garantie procédurale n'a pas été respectée, il convient autant que possible de remettre la personne lésée dans la situation qui aurait été la sienne si l'exigence en cause n'avait pas été méconnue. S'agissant d'une violation du droit d'être entendu par exemple, la réparation consiste à renvoyer le dossier à l'autorité intimée pour qu'elle rende une nouvelle décision après avoir donné à la personne intéressée l'occasion de s'exprimer. Ceci n'est toutefois pas possible dans le cas de l'art. 6 par. 3 let. c CEDH, puisque la "première heure" est passée et que ni l'assistance fournie ultérieurement par un avocat ni la nature contradictoire de la suite de la procédure ne peuvent porter remède à cette atteinte. La Cour européenne des droits de l'homme a ainsi considéré que, dans une telle situation, la forme la plus appropriée de redressement était, pourvu que le requérant le demande, un nouveau procès conforme aux exigences de l'art. 6 par. 1 CEDH; la Cour s'est au demeurant abstenue de spéculer sur l'impact qu'aurait eu sur l'aboutissement de la procédure au fond la possibilité pour le requérant de se faire assister par un avocat dès son arrestation, ni a fortiori sur les conditions de la détention préventive.
Il apparaît dès lors que la mise en détention provisoire n'est pas pour autant illégale. Il ne serait en effet guère concevable qu'un prévenu sur lequel pèsent des soupçons suffisants de culpabilité et un risque concret de fuite, de collusion ou de réitération, puisse échapper à une détention préventive matériellement justifiée et, le cas échéant, se soustraire à la justice pour des raisons formelles. Le vice allégué ne saurait donc avoir pour conséquences l'invalidation du mandat d'arrêt et la libération immédiate du recourant, ce d'autant que ce dernier n'a pas remis en cause les conditions matérielles de sa détention. On peut en outre relever que le mandat d'arrestation ne s'appuie pas uniquement sur les déclarations faites par le recourant devant la police, mais également sur d'autres éléments du dossier, à savoir notamment l'audition du prévenu par le Juge d'instruction, la plainte émise par les lésés, une video de l'infraction, le casier judiciaire de l'intéressé et son interpellation au volant du véhicule volé.
4.2 La Chambre d'accusation n'a pas donné suite à la requête du recourant tendant à écarter de la procédure les procès-verbaux établis sans la présence d'un avocat. Celui-ci réitère sa demande devant le Tribunal fédéral. Le fait de savoir si les déclarations faites par le recourant devant la police doivent être ou non retirées du dossier relève toutefois de l'appréciation des preuves, qui ressortit au juge du fond. Il appartiendra donc au recourant, s'il estime que ces procès-verbaux pourront lui porter préjudice dans l'examen de sa culpabilité, de requérir de l'autorité de jugement qu'elle retire ces pièces du dossier afin de sauvegarder son droit à un procès équitable. Cette question n'a au demeurant pas d'incidence sur la justification de la détention du recourant, qui constitue en réalité le seul objet de la présente contestation.
5. Il résulte de ce qui précède que le recours, entièrement mal fondé, doit être rejeté. L'issue du litige rend la requête d'effet suspensif sans objet. Dès lors que le recourant est dans le besoin et que ses conclusions ne paraissaient pas d'emblée vouées à l'échec, l'assistance judiciaire doit lui être accordée (<ref-law>). Le recourant requiert la désignation de Me Grégoire Mangeat en qualité d'avocat d'office. Il y a lieu de faire droit à cette requête et de fixer d'office les honoraires de l'avocat, qui seront supportés par la caisse du Tribunal fédéral (<ref-law>).

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est rejeté.
2. La demande d'assistance judiciaire est admise. Me Grégoire Mangeat est désigné comme avocat d'office du recourant et une indemnité de 1'500 fr. lui est allouée à titre d'honoraires.
3. Il n'est pas perçu de frais judiciaires.
4. Le présent arrêt est communiqué au mandataire du recourant, au Ministère public et à la Chambre d'accusation du canton de Genève.
Lausanne, le 19 avril 2010
Au nom de la Ire Cour de droit public
du Tribunal fédéral suisse
Le Président: La Greffière:
Féraud Mabillard