Crystal oscillators in PICs and AVRs are supply voltage dependant for a given crystal frequency , and also very dependant of the value of the capacitors from either side of the crystal to ground.
The crystal itself is also important, as it needs to be a parallel mode crystal.
Usually, the datasheet for the Pic or AVr will tell you what the optimum capacitor values should be .
You can measure the frequency with a X10 Cro probe connected to the output pin of the oscillator, but the best most reliable way
is to use the CLKOUT option which most PICs and AVRs have and simply measure the freqency on the CLKOUT pin.