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?
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$.