По Фасмеру - через польск. pietruszka, чеш. реtrјеl - то же из ср.-в.-н. petersi^lje от лат. petroselinum, греч. petrosљlinon.
Греческий корень «petr-» означает «камень». При чём здесь камень? Или это просто совпадение?
upd, спасибо
mich_from_jrslm:
Название овоща присходит от греческого "петроселинон", состоящего из 2 корней: "петрос" (камень, скала) и "селинон" (сельдерей). То есть для древних греков, видимо, петрушка воспринималась как "разновидность сельдерея, которая растет на каменистой почве".