I'd recommend a simple phone call. "Hiya Bob, thank you for your time in getting us to this offer of employment. Circumstances have changed and it looks like I will not be able to work for your firm. I apologize for the inconvenience. ... Yes, Bob, I appreciate that this puts you in a bit of a lurch. Please accept my apologies. Would you like me to recap this conversation in a letter? Thank you Bob. Best of luck finding a candidate."
I don't particularly suggest telling them that you're taking employment elsewhere. That's something you tell your friend. They're not your friend. If you worked there, they would still not be your friend. Bob might eventually have become your friend, but right now Bob is a corporate officer of a company which underbid for your services. You don't particularly owe them explanations or excuses.
At-will employment is a two-way street.