How Can I get and add new company via Rest API

The REST API will have separate resources for Contacts and Companies. They will likely end up looking/feeling different than what folks may be used to with the XML-RPC API.

So, in this case, hypothetically, AccountId would not be a field on Contacts but would rather be a field on Companies. (I use this as an illustration; it’s not guarantee of the future.)