Faits: A. Le 8 mai 2007, A._ a demandé d'être inscrit au tableau des avocats stagiaires du canton de Vaud à partir du 1er juillet 2007, son futur maître de stage étant l'avocat B._. Ce dernier, titulaire d'une licence et d'un doctorat en droit de l'Université de Lausanne, a obtenu le brevet d'avocat dans le canton de Vaud le 2 juillet 2001. Il a été inscrit au registre des avocats vaudois du 17 au 31 juillet 2002, puis à nouveau dès le 18 décembre 2006. Dans l'intervalle, il a été inscrit au registre des avocats genevois du 23 août 2001 au 13 décembre 2006 et a travaillé pour l'Etude C._. Le 31 mai 2007, la Cour administrative du Tribunal cantonal vaudois (ci-après: la Cour administrative) a rejeté la demande de A._, car son futur maître de stage n'était pas habilité à former un stagiaire dans le canton de Vaud, dès lors qu'il n'était pas au bénéfice des cinq ans de pratique dans le canton exigés par la législation vaudoise. Par arrêt du 1er octobre 2007, le Tribunal administratif vaudois - devenu depuis lors la Cour de droit administratif et public du Tribunal cantonal vaudois - (ci-après: le Tribunal administratif) a partiellement admis, dans la mesure où il était recevable, le recours formé par A._, B._ et l'Etude C._ contre la décision de la Cour administrative du 31 mai 2007. Les juges cantonaux ont considéré en substance que le fait que B._ n'ait pas été inscrit au registre des avocats vaudois pendant cinq ans n'empêchait pas qu'il puisse démontrer, d'une autre manière, qu'il bénéficiait d'une pratique judiciaire dans le canton suffisante. Il appartenait à la Cour administrative d'inviter B._ à prouver la réalité de sa pratique vaudoise. La décision de la Cour administrative du 31 mai 2007 a donc été annulée et la cause renvoyée à cette autorité pour nouvelle décision après complément d'instruction. Le 22 octobre 2007, la Cour administrative a une nouvelle fois refusé d'inscrire A._ au tableau des avocats stagiaires du canton de Vaud. Elle a retenu que B._ n'avait pas une pratique d'au moins cinq ans dans le canton de Vaud au regard des activités dont il s'était prévalu. B. A._ et B._, d'une part, ainsi que la Commission de la concurrence, d'autre part, ont recouru contre la décision de la Cour administrative du 22 octobre 2007. Par arrêt du 20 décembre 2007, le Tribunal administratif, tout en renvoyant pour partie à la motivation figurant dans son arrêt du 1er octobre 2007, a rejeté "le recours". Il a notamment considéré que le fait d'avoir accompli, dans le canton de Vaud, cinq ou dix procédures judiciaires et une dizaine de mandats de conseil juridique ne saurait être assimilé à une pratique de cinq ans dans le canton, même si l'on se référait à titre de comparaison à la situation d'un avocat établi dans ledit canton qui partagerait son activité entre plusieurs cantons ou dont la pratique judiciaire serait limitée. C. A._ et B._ forment un recours en matière de droit public contre les arrêts rendus par le Tribunal administratif les 1er octobre et 20 décembre 2007. Ils concluent, sous suite de frais et dépens, à ce que le Tribunal fédéral dise que B._ est autorisé à engager des avocats stagiaires dans le canton de Vaud et ordonne aux autorités vaudoises de procéder à l'inscription de A._ au tableau des avocats stagiaires, avec effet au 1er juillet 2007, respectivement avec effet immédiat. La Commission de la concurrence, tout en déclarant adhérer aux conclusions des recourants, interjette également un recours en matière de droit public contre l'arrêt du Tribunal administratif du 20 décembre 2007. Elle demande au Tribunal fédéral, sous suite de frais, de constater que la loi fédérale sur le marché intérieur est applicable au cas d'espèce et que l'arrêt du Tribunal administratif du 20 décembre 2007 restreint indûment l'accès au marché, de sorte qu'il est contraire à ladite loi. A._ et B._ concluent à l'admission de ce recours. Le Tribunal administratif et la Cour administrative concluent au rejet des deux recours. L'Office fédéral de la justice a déposé des déterminations limitées à la loi sur les avocats et est parvenu à la conclusion que cette loi n'avait pas été violée. 