That is a pretty complex scenario and answers to your questions depend greatly on the specifics. Will the NetBIOS name change? Will the domain structure change? Are usernames changing?
Usernames for SharePoint permissions are stored per site, in the content databases as "Domain\Username" (unless you're using Claims). If the domain name isn't changing, you should be OK. You can also use the stsadm -o migrateuser command if the domain or
username will be changing. Also, you might want to consider Axceler ControlPoint, they have a "replace user" function and can search the entire farm.
If you have the option, you should stand up the new domain with the old, create a two-way trust and take care of permissions in SharePoint and other systems and then turn off the old domain when everything is working as it should.
Wahid Saleemi Sr. Consultant, Avanade http://www.wahidsaleemi.com