A relay circuit requires a transistor (or two transistors in Darlington Pair configuration) as a driver. Look at this circuit
Experiments with PIC16F628A: Experiment No. 9: DC Motor Speed Control using PWM to drive a motor; you can replace the motor with a relay. Here, is what you can try. Replace the DC motor with a 12 V relay, and change the power supply to 12V. And then, when you give 5V to the input pin, the relay should turn ON. If that works then you should be able to control the relay with PIC16F628A too.
I don't know what 40-pin evaluation board are you talking about, but if that board would be able to program a PIC16F628A, it must be mentioned on it's user's guide.
- Raj