If you are supplying +5V to your project using the +5V from ICD2 then you'll need a power supply of 12V 800mA to power up both your circuit and the PIC, assuming your project does not requires more than 800mA. If you use higher supply voltages, then the 5V regulator on the ICD2 circuit board will get very hot and eventually overheated. So if your project draw a lot of current, keep the input voltage as low as possible.
If you just want to program the PIC chip alone, or your project is powered using yet another supply, then any power supply with 12-16V output is fine as PIC needs only a few mA just for programming.
Typical laptop power supply can be used if the voltage output is within 12-16V.