When people say "an algebra" do they always mean "an algebra over a field"? I don't have much experience with abstract algebra. I'm only versed in linear algebra and vector spaces, and have had a tiny introduction to algebras over fields. 
However, this question is a purely terminological one: When people say "an algebra" do they always mean "an algebra over a field"?
If not, what other things can it refer to? 
 A: This is a list of the most common descriptions of an "algebra," but is not exhaustive.

1 .  An algebra of sets.

A collection of subsets of a given set closed under unions and complements.

2 .  An associative algebra over a commutative ring.

Let $R$ be a commutative, not necessarily unital ring.  An algebra over $R$ is a ring $A$, not necessarily commutative or unital, together with an $R$-module structure on $A$, such that scalar multiplication by $R$ is compatible with the ring multiplication in $A$:
$$r \cdot (a_1a_2) = (r \cdot a_1)a_2 = (a_1 \cdot r a_2)$$
If $A$ has an identity, then to give the structure of an $R$-algebra on $A$ is the same as giving a ring homomorphism $R \rightarrow A$ whose image lies in the center of $A$: given the $R$-module structure on $A$, one defines the homomorphism $R \rightarrow A$ by sending $r \in R$ to $r \cdot 1_A$.
If $R$ has an identity, then $A$ is usually assumed to be unitary as an $R$-module, which is to say $1_R \cdot a = a$ for all $a \in A$.  If both $R$ and $A$ have an identity, then saying $A$ is unitary as an $R$-algebra is the same as saying that the homomorphism $R \rightarrow A$ sends $1_R$ to $1_A$.
If $A$ and $R$ are both commutative rings with identity, then a unitary $R$-algebra structure on $A$ is the same thing as a ring homomorphism $R \rightarrow A$ which sends $1_R$ to $1_A$.  This is how algebras are typically understood in commutative algebra.

3 .  Lie algebra over a field.

Let $k$ be a field, and let $\mathfrak g$ be a set with two operations $+$ and $\cdot$ satisfying all the axioms of a (not necessarily commutative or unital) ring, except $\cdot$ is not assumed to be associative.  Write $[X,Y]$ for $X \cdot Y$.  Assume that the following equation holds for all $X, Y, Z \in \mathfrak g$:
$$[X,Y] + [Y,Z] + [Z,X] = 0$$
The structure $\mathfrak g$, together with a unitary $k$-module structure on $\mathfrak g$, such that scalar multiplication from $k$ is compatible with the multiplication $[-,-]$ in $\mathfrak g$:
$$c \cdot [X,Y] = [c \cdot X,Y] = [X, c \cdot Y]$$
is called a Lie algebra over $k$.
Examples:
1 .  The Borel sets of a topological space $X$.  These are subsets of $X$ obtained by taking countable unions and complements of open sets in all possible combinations.
2  .  Let $R = \mathbb C$, and let $G$ be a Hausdorff topological group with the property that every neighborhood of the identity contains a compact open subgroup of $G$.  Then $G$ is locally compact and has a Haar measure $\mu$.  The $\mathbb C$-vector space $C_c^{\infty}(G)$ of locally constant and compactly supported functions $G \rightarrow \mathbb C$ can be made into a unitary $\mathbb C$-algebra by defining multiplication as convolution:
$$f \ast g(x) = \int\limits_G f(y)g(y^{-1}x) d\mu(y)$$
This is called the Hecke algebra of $G$.  It is usually not commutative.  If $G$ is compact, it is unital.
3 .  Let $\mathfrak g$ be the $k$-vector space of linear transformations of a vector space $V$ to itself.  Then $\mathfrak g$ is a Lie algebra over $k$ if we define $[\phi,\psi] = \phi \circ \psi - \psi \circ \phi$.
A: Fields are very special commutative rings with unit (that I'll just call rings). A general definition is: if $A$ is a ring, an $A-$algebra is a ring $B$ together with a ring homomorphism $f:A \to B$ (this is, for instance, the definition of the classic "Commutative Algebra" by Atiyah and Macdonald). Note that then we can define an "action" of $A$ on $B$ via $a\cdot b:=f(a)b$, so there are actually more explicit definitions, but this is the most succinct I know. Note that if $A$ is a field, $f$ is injective, so an $A-$algebra (for $A$ a field) is just a ring that contains $A$ as a subring.
Note that there are many common and important cases of (in general) non-commutative algebras as well! Lie algebras, Hopf algebras and so on. So they require a different definition. But they are usually considered in a different setting.
A: It really depends on the context: most of the time it's used for algebras over rings and fields. Sometimes it is used in the most general context of universal algebra as a generic word to talk about a model for an algebraic theory: for example, groups are algebras for the (syntactic) theory of groups.
A: Quite often that is what is meant, yes: algebras over fields. Often, but not always, associative.
However, in commutative algebra it is also common to talk about (associative, with identity) algebras over commutative rings. In this case, a ring $A$ (commutative or not) is called an $R$ algebra over a commutative ring $R$ if there is a unital ring homomorphism from $R$ into the center of $A$.
In my experience, the latter one is the largest scope that is in common use, and is not unusual. "Over a field" probably is used more frequently, though.
In the field of universal algebra, "algebra" can refer to a set with operations of various -arity, but this use is fairly isolated to the field.

There are some folks in the wings who think I really ought to say something about nonassociative algebras and algebras without identity. The description using homomorphisms does not suit for defining such algebras, but the usual "describe-the-action-with-axioms" definition works. Again, without context, it is highly unlikely that someone would call these simply "algebras," but they would probably instead add more adjectives.
For example Lie algebras and Jordan algebras are important nonassociatve algebras, but they would probably never be referred to simply as an "algebra" where they are found.

Boolean algebras are another interesting case. Again, you'll probably never find these called simply "an algebra." What makes the case interesting is that they have more than one identity as an algebra. First and foremost, it probably fits the category of "type described by universal algebra" mentioned above, using meet and join, a lattice-theoretic description. However, it also has a natural boolean ring structure, and this ring is actually a subalgebra of $\prod_{i\in I}F_2$ for some index set $I$.
