Braintree is one of the easier gateways to configure, and decreases your liability for customer data because credit card information is never 'touched' by your site. The information is entered into a form embedded in your site, so it matches the rest of your skin and customers don't have to leave your site.
Obtain your API credentials. At the time of this writing, that was done by:
Log into your Braintree account
Click on Account -> My User at the top of the page
Scroll to the bottom of the page and click on 'View Authorizations'
If no keys appear, click 'Generate New API Key'
Obtain the Public Key (near the top of the page), Private Key (you must click the 'View' link to see this), and Merchant ID (near the bottom of the page)
Log into your store's admin console and go to Configuration -> Site Setup Wizard in the top navigation.
On the Site Setup Wizard page, scroll down to the Payment Processing Solutions section and click the 'configure' link next to Braintree. The Braintree configuration window appears.
Fill in the 3 values you got from your Braintree account. Note that 3dSecure is not enabled by default on new Braintree accounts. If you want to use that option, you'll need to work with Braintree support to enable it on your account before setting that option to 'Yes' here in the admin console.
Click the 'Save and Close' button, then click the radio button next to Braintree.
Make sure that 'Credit Card' is checked in the Credit Cards & Other Payment Methods section.
Finally, click 'Save' at the top or bottom of the page and your site should be configured to accept credit cards through Braintree!
Braintree cannot participate in a backup gateway relationship, either as the primary gateway or the backup gateway.
If setup is complete and correct but you are still getting a message: "Our Credit Card processor is currently experiencing difficulties. Please try another payment method or contact us for assistance."
Check that your Braintree account has been fully approved.
Check that your Braintree account USER has Transaction permissions.