Yes, cap on each pin: Vcc, AVcc, Aref. Aref is cap only, do not connect to 5V.
Here are three ways to drive a relay coil. Keep the inductor spike off the arduino pin.