ICSP Circuit: Vpp (13V) and Vdd (5V) on Pic microcontroller MCLR pin
Yes, it's perfectly normal to have a resistor on MCLR to Vdd, but also raise MCLR (this time in it's Vpp role) to the programming voltage during programming.  I usually use 20 k&Omega; for that.  It's a good tradeoff between being low enough impedance to not pick up noise, but high enough that most programmers out there will have no problem driving the line to the Vpp level.  Note that can be up to 13 V on some PICs.

You also need to consider the current getting dumped onto the 5 V supply rail.  With 13 V for Vpp, 5 V supply, and 20 k&Omega; pullup resistor, 400 &micro;A will go onto the 5 V rail.  If the rest of the circuit draws at least that, then there will be no problem.  The power supply will just supply 400 &micro;A less.  If it's just the PIC, you may have to consider clamping the 5 V supply, using a higher pullup resistor, or putting a diode in series with the resistor.  In practise most of the time 400 &micro;A is small enough that other parts absorb the current, and most newer PICs use a lower programming voltage anyway.

For more background and general demystification of designing to in-circuit programming see my writeup at http://www.embedinc.com/picprg/icsp.htm.