im not sure if gentlies are absolutly REQUIRED to get married. anyway the "marriage" paper or whatever you get from the state has nothing to do with the halahic marriage under Jewish law (for Jews). If your Jewish you can be married under Jewish law , but not under civil law and it would be legit.
once again im not exactly sure about the Noahide law, but the problem for many gentile people is that if a girl had relations with a guy ( which is concidered them being married) then she would have to get some divorce before she sleeps with another man, and if not then its ADULTRY - which supposed to be punishible by death by gentile (Noahide) law.