I have a related issue, since I have some income which is large enough to matter and hard to predict.
Start with a best guess. Check what tax bracket you were in last year and withhold that percentage of the expected non-withheld income. Adjust upward a bit, if desired, to reflect the fact that you're getting paid more at the new job. Adjust again, either up or down, to reflect whether you were over-withheld or under-withheld last year (whether the IRS owed you a refund or you had to send a check with your return).
Repeat that process next year after next tax season, when you see how well your guess worked out.
(You could try pre-calculating the entire tax return based on your expected income and then divide any underpayment into per-paycheck additional withholding... but I don't think it's worth the effort.)
I don't worry about trying to get this exactly correct. I don't stress about lost interest if I've over-withheld a bit, and as long as your withholding was reasonably close and you have the cash float available to send them a check for the rest when it comes due, the IRS generally doesn't grumble if your withholding was a bit low.
(It would be really nice if the IRS paid us interest on over-withholding, to mirror the fact that they charge us interest if we're late in returning our forms. Oh well.)
Despite all the stories, the IRS really is fairly reasonable; if you aren't deliberately trying to get away with something, the process is annoying but shouldn't be scary. The one time they mail-audited me, it was several thousand dollars in my favor; I'd forgotten to claim some investment losses, and their computers noticed the error.
Though I still say the motto of the next revolution will be "No taxation without proper instructions!"