bevinator: Yep, I've used both the GOG and Steam version to play with both GOG and Steam players. The only issue that generally arises is that Steam usually gets new patches a day or two before GOG does, so there may be short interruptions in the future, because the dev team isn't quite finished with Terraria yet.

If you run into a connection problem, it's almost always due to port forwarding issues. The host will usually have to look up specific instructions for their router model.