This might be a most basic question, but what does it mean to have a Braintree server? I understand there is some code which needs to run on a server, which means the 'server' has to be always 'on'?
I've stumbled across Heroku, but are there alternatives? Can I use Firebase, too?
A server is simply any computer that provides data or services to another computer (or mobile device) over a network, such as the Internet. A server runs special software that allows it to process commands and return data sent from requesting applications. Your laptop, desktop, or even Raspberry Pi could be configured to be a server as long as it's connected to a network and is configured to receive and respond to network traffic. See this page for a more thorough explanation.
In the context of the question, a "Braintree server" is any server that has Braintree's server-side API installed on it and is exposed to a network. Services like Amazon AWS or Heroku are considered Platforms as a Service (PaaS). They provide you with remote access to a server that already has a development environment setup for you. You would simply need to install Braintree in your choice of environment. For example, in Node.js the command is as simple as this:
npm install braintree
Firebase is considered a Backend as a Service (BaaS). It not only manages the physical hardware and dev environment, it also manages data storage and synchronization. It offers a rich feature set, but can be more complicated to customize.
You could also get started with a very basic cloud option like DigitalOcean. This is considered Infrastructure as a Service (IaaS), because you receive access to a blank server which you can then customize to your heart's content. Create a droplet, install Python, Ruby, Node.js etc, then install Braintree and get coding.
Any of these services will make sure that your server is "always on". I personally recommend DigitalOcean. You will have to do a lot more of your own setup, but you'll learn much more in the process.