Faits: A. Le 7 novembre 2011, le Ministère public du canton de Genève a ouvert une enquête pénale à l'encontre de A._ notamment pour faux dans les titres, gestion déloyale et blanchiment d'argent. Après un transfert du for de la poursuite pénale vers le canton de Neuchâtel le 2 février 2012, le prénommé s'est trouvé prévenu d'infractions aux art. 146, 158, 165 et 251 CP. Dans ce cadre, le Ministère public du canton de Neuchâtel (ci-après: le Ministère public) a ordonné, le 16 février 2012, les séquestres de trois véhicules qui étaient ou avaient été immatriculés au nom de la société B._ SA dont A._ est l'administrateur unique. Une Bentley GB Mulsanne non immatriculée depuis le 7 février 2012 a notamment été saisie, en garantie des frais de justice liés à la procédure pénale ouverte contre le prénommé (art. 263 al. 1 let. b du code de procédure pénale suisse du 5 octobre 2007 [CPP; RS 312.0]). Par arrêt du 11 avril 2012, l'Autorité de recours en matière pénale du Tribunal cantonal du canton de Neuchâtel (ci-après: le Tribunal cantonal) a rejeté le recours formé par A._ contre cette décision. Elle a considéré en substance que le séquestre du véhicule formellement immatriculé au nom de B._ SA était justifié par le fait qu'il s'agissait en réalité d'un bien appartenant à A._; le séquestre respectait en outre le principe de la proportionnalité. B. Agissant par la voie du recours en matière pénale, A._ et B._ SA demandent au Tribunal fédéral d'annuler l'arrêt cantonal ainsi que l'ordonnance de séquestre du 16 février 2012, en ce qu'elle porte sur le séquestre du véhicule Bentley GB Mulsanne, et de restituer le véhicule à son propriétaire. Ils se plaignent notamment de violations de l'interdiction de l'arbitraire (art. 9 Cst.) et de la garantie de la propriété (art. 26 Cst.). Le Ministère public et le Tribunal cantonal renoncent à présenter des observations. Par ordonnance du 15 mai 2012, le Président de la Ire Cour de droit public a rejeté la requête d'effet suspensif, présentée par les recourants.