Using the PICkit3 and PIC18F4550
I found the answer, and my gosh it was silly. The first part is that I had the pins in the reverse order. I didn't properly look at the datasheet to see where pin 1 was. It is by the arrow.

Second of all, I had connections to the wrong place. I followed the diagram below, and it worked well. Note that Vdd is 5V (supplied by the PICkit 3) and MCLR/NOT(Vpp) is pin 1.

If I had enough rep, I would post the diagram.