1) Rosin Core Solder (NOT from Radio Shack, either).

2) Heat - I prefer using a LOT of heat (230 watt gun!) and "get on and get off fast". This way, you actually put LESS heat in components than using, say, a 30 watt iron and sitting there all day trying to get the solder to flow, allowing the heat to spread all over. Like I say, you don't HAVE to do it my way... but that's how I'v been soldering for decades. Just make sure the solder flows and both the board and "barb" of the relay/relay socket gets hot enough for the solder to bond.

3) Oh, don't touch the iron tip - it gets hot!