Different ROMs need different GApps? I am currently using  ParanoidAndroid rom and I am switching to Cyanogen 10 on my Galaxy Nexus.

Do I need to download/install a new Gapps .zip file?
It depends on the actual android version of the ROM you flashed. it the ParanoidROM and Cyanogenmod ROM are both Android 4.2 then you don't need a new set of gapps, if there aren't then if might just be safe to get a new set of gapps