Hi Cal,
Jeff (loftus) pretty much nailed it with respect to simultaneously adjusting shutter speed and aperture for a given exposure, but you may also want to consider what adjusting each in isolation does to your exposure.
Lets say that you have a typical wide angle/close focus subject so the subject is very close to you and will be primarily exposed by your strobe while the distant background will be illuminated by ambient light. You also determine that the optimal exposure will be 1/60s at F8 with strobe power set at 1/2.
-if you change the shutter speed while leaving the aperture and strobe power the same you will change the background exposure while leaving the foreground untouched. So, if you change you aperture to 1/120s then your background will be 1stop underexposed but you foreground will be unchanged. This is because your foreground is primarily illuminated by your strobe. Since the strobe flash is so much faster (~1/1000s) than your shutter speed, the entire flash duration will be captured by the sensor regardless of what shutter speed you choose (within reason of course).
-if you change aperture while leaving strobe power and shutter speed constant, then you entire exposure will be affected. So, changing your aperture from F8 to F5.6 will result in both your foreground and background being overexposed by 1 stop. As mentioned by Jeff, you're depth of field will also be affected (reduced).
-if you change strobe power, but leave aperture and shutter speed unaltered, then you foreground expose will change, but your background exposer will be unaffected. Decreasing strobe power from 1/2 to 1/4 will result in a foreground that is underexposed by 1 stop, but your background will be unaltered.
There are many other things that will influence results, but this is a good starting point.
With respect to how slow of shutter speed you can use... that's pretty subjective. A general rule of thumb is 1/focal length (35mm equivalent) so if you using a 12mm lens on a DX sensor you should be able to get away with a shutter speed down to 1/18s. That is, if your careful and have steady hands (and good buoyancy). However, don't be afraid to try slower if the situation demands it. When shooting film in dark temperate waters, I was often forced to shoot at 1/8 or even 1/4 at F4 to F5.6 to get the exposure. There were lots of tossers, but a few worked out. For macro, shutter speed generally doesn't matter as your primary source of illumination is your strobes which will freeze the motion. But again, this depends on what you want your background to look like (inky black vs deep blue).
Cheers,
Mike