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
Yes you need to download gapps from here: GApps.
Just choose the correct version of Cyanogen mod that you have.
Note: Cyanogenmod 10 has another gapps then Cyanogenmod 10.1.