First off, it depends on the wattage of the lights. I believe Wal-Mart sells both 55 watt and 100 watt lights. Lets assume you're getting the 100 watt light, because if you wire for that you'll be just fine with either.
So, two 100 watt lights = 200 watts = 17 amps @ 12 volts. The lights actually operate at about 13 volts, but wire it to handle 20 amps and you'll have a nice safety margin.
You should not wire your fog and driving lights together, because you want to be able to turn on one or the other. In particular, if you are in foggy conditions you do NOT want to turn on your driving lights as they'll just make your visibility WORSE! That means you need two switches, two relays, etc.
Obviously you don't need 50 amp relays. The standard automotive relays, available cheaply at every auto parts store, are usually rated for 30 amps and that is clearly plenty for your situation. Sometimes you can find 50 amp relays for very little more and they will work just as well. In any case, as long as the relay is rated for at least 20 amps, there's no need to pay extra for a higher rating.
As Eagle said, the switch carries very little load--probably less than a single amp. So 20 gauge wire from the switch to the relay would be plenty, though I rarely bother with anything smaller than 16 gauge myself.
From the battery to the relay, and from the relay to the lights, you'll need a circuit that can carry 20 amps. 10 or 12 gauge depends on how long the run is. If you're front-mounting the lights (rather than on the roof) then the run should be short enough that 12 gauge will work fine. In fact, if you get the type of relay that has two normally open terminals (rather than one normally open and one normally closed) then you can run a 14 gauge wire from each terminal to each light, since each individual light will be drawing less than 10 amps.
Good luck!