I know the definition of an algebra over a field.
Definition An algebra over a field $\mathbb{F}$ is a vector space $A$ over $\mathbb{F}$, together with a bilinear map $f: A \times A \rightarrow A$, $f(x, y) = xy \, \forall x, y \in A$.
Usually one studies algebras over fields where the product satisfies some further properties.
But what is the definition of an algebra over a vector space? A definition and an example would be much appreciated.
There isn't any definition that replaces the field with a vector space. If that is what you're looking for, you're out of luck. That probably hasn't been studied.
There is, however, the notion of the most general $K$-algebra generated by a $K$-vector space. You would want to look up the tensor algebra of a vector space V to learn about this.
Several types of interesting algebras can be derived as quotients of that algebra, too. For example, there is the symmetric algebra of V, the exterior algebra of V, and, if you have a symmetric bilinear form on V, the Clifford algebra of V (with respect to the bilinear form.) There is also a version for alternating bilinear forms.