How does OSCCON being set to 00111000 give me 500KHz?
You need to look at what the individual OSCCON bits mean and look at the diagram of the clock description. It usually shows multiplexing blocks that select one of multiple inputs based on contlrol bits used.
In this instance bit7 = 0, means the 4xPLL (basicaly multiplies input freq by 4) is off,
bits 6 to 3(named IRCF) = 0111 If you look at the mux block in the picture it selects one of umpteen frequencies from the post scaler, here it's the 500kHz input
bit 2 does nothing
bits 1 and 0 are set to 0 which makes the clock select mux chose the the input based on the FOSC config word.
Its seems you knew most of that anyway, from your post.
Also how does a 500KHz clock speed give me 125k instructions per second?
Most pics take 4 cycles to complete one instruction so its 500k/4