You should create a 2 way trust relationship to begin with.
Then set up DNS replication of DNS zone between domains.
a)You should add the other company domain to the other dns suffix search list.
b)You will need to use universal groups, so they can be used on the other domain. This Technet article explains groups scope
c)You will have many task for that:
- kerberos task. Sharepoint server will need to be able to reach DC of the other domain
- You will need to use groups and co that include users from both domain
- Internet explorer: need to set the sharepoint site as intranet zone, through GPO for example. So users will do integrated authentication
- People picker tuff
This depends on how those Samba servers are configured to handle the Username/UID and Groupname/GID mapping. This is done with the idmap directives. There are a couple of ways to configure Samba to handle this, but which one is in use will impact how they're able to handle cross-domain trusts and accounts migrating between domains.
The manual for this is here:
http://www.samba.org/samba/docs/man/Samba-HOWTO-Collection/idmapper.html
If they're using the default Winbind back-end, a database that matches Domain\Username pairs to local UIDs, when accounts migrate across domain boundaries they'll appear as new users to Samba. This is because their SID changes as they cross the domain boundary. However, this model does allow cross-domain usage over a trust.
If they're using the the RID back-end, the Samba server will NOT be able to allow access to users in different domains. If this is the case, you're probably already aware of it. When users move out of the domain the Samba server exists in, they will lose all access to it.
If they're using an LDAP server as a way to share Username/UID mappings across multiple Samba servers, the same restrictions as the default back-end apply. However, each Samba server will have the same Username/UID mapping. The upside is that you might be able to directly edit the LDAP server after migration to a new domain to ensure that the same Username/UID mapping is preserved.
The last option is perhaps your best bet for maintaining compatibility during your staged migration. However, if they're not already using an LDAP server as a central repository it will get much trickier.
Best Answer
It is relatively complex and is outlined in this excellent TechNet article.
Honestly, doing this without a site-to-site VPN is a BAD idea for a lot of reasons. I'd strongly reconsider that stance. If you can't afford proper hardware VPN endpoints, you could always use something like OpenVPN at each end. It even comes in a virtual appliance for super-easy delivery.