Is there a formal notion of equivalence between structures with potentially different signatures? What is the appropriate notion of equivalence between structures with potentially different signatures?
Consider an example from abstract algebra. Whether a group is defined as a pair $(X,*),$ or as a triple $(X,*,e)$ where $e$ is the identity, probably shouldn't influence the theory of groups. These two descriptions are essentially "equivalent" in some sense.
On the other hand, whether a magma is defined as a pair $(X,*),$ or as a triple $(X,*,e)$ where $e$ is allowed to be any element of $X$, probably should influence the theory, because we've chosen a distinguished element and presumably this will influence what we mean by a "magma isomorphism," for example.
As another example, consider that a topological space can be viewed as a pair $(X,\mathcal{O})$ such that $\mathcal{O} \subseteq \mathcal{P}(X)$ is closed with respect to arbitrary unions etc. Alternatively, it can be viewed as a pair $(X,\mathcal{K})$ such that $\mathcal{K} \subseteq \mathcal{P}(X)$ is closed with respect to arbitrary intersections etc. Note that, in the case where $X$ is of finite cardinality, a pair $(X,\mathcal{X})$ will be a topological space in the first sense if and only if it is a topological space in the second sense. See also, finite topological space. Nonetheless, the two descriptions are usually considered equivalent.
So here's my question. Consider two structures, $X$ and $Y$. I want to make rigorous the question, "are they essentially the same?" Supposing that such a question is ill-posed, I want to make rigorous the question, "do they define essentially the same group?" Importantly, consider the structures "in a vacuum," and not viewed as models of any particular theory.
 A: The language of category theory provides a very rigorous setting for such, and more general, equivalences. Basically, under any reasonable definition of algebraic structure (with whatever signature) there will be associated a natural notion of morphisms and these will form a category (sometimes a weak category, but let's forget about that subtlety). Now, for two categories there is a notion of isomorphism (which is the usual notion, a bijective function that preserves the structure). But categories in the wild are very rarely isomorphic while they still may be equivalent. Categorical equivalence is a bit more difficult to describe since it requires the notion of natural transformation (which can be compared to the notion of homotopy). The definition will appear in any text on categories. 
To answer your question in the context of the above, it is very often the case the algebraic or topological structures defined using very different signatures or underlying machinery turn out to give rise to equivalent categories. Examples include: groups defined with a signature including an identity constant or not (the resulting categories in this case will actually be isomorphic), heaps and groups (the resulting categories will be equivalent but not isomorphic), sober space and spatial locales (yields equivalent but non-isomorphic categories), topological spaces defined using open sets vs. closed sets vs. Kuratowski closure operation (will yield isomorphic categories) and many more. 
Of particular importance in modern homotopy theory (and other areas) is a more subtle situation where the relevant categories are not equivalent but the relevant $\infty$-categories are equivalent. This requires much more machinery than the above so I'll just mention the famous example due to Quillen that the $\infty $-category of simplicial sets is equivalent to the $\infty $-category of the homotopy theory of topological spaces. 
Buzz words: Isomorphism of categories, equivalence of categories, Quillen model structures. 
A: How about this:
Let $\mathfrak A=(A,\Sigma,(f_\mathfrak{A})_{f\in \Sigma})$ be a structure in which $A$ is the domain, $\Sigma$ is a signature, and $f_{\mathfrak A}$ is a family of interpretations of the operations of $\Sigma$.
Let $\mathfrak B=(B,\Xi,(g_\mathfrak{B})_{g\in \Xi})$ be a different structure.
Define a "structure morphism" $\mathfrak A\to\mathfrak B$ to be a function $\mu:A\to B$ such that there exists a family $(\phi_f)_{f\in\Sigma}$ of formulas in the language of $\Xi$, such that the number of free variables of $\phi_f$ is the arity of $f$ and such that for each $f\in\Sigma$ it holds that
$$ \forall a,a_1,\ldots,a_n \in A:\quad 
\Big[\mathfrak A\vDash a=f(a_1,\ldots,a_n)\Big] \iff
\Big[\mathfrak B\vDash \phi_f(\mu(a),\mu(a_1),\ldots,\mu(a_1))\Big] $$
Then the composition of structure morphisms is clearly a structure morphisms, and we have a category of theory-less structures and structure morphisms where isomorphic objects could be considered to be "essentially the same".
Alternatively, you might want to consider the formulas $(\phi_f)_{f\in\Sigma}$ to be part of the morphism, but them you probably want to quotient out equvialent formulas, such that $(\mu,(\phi_f)_{f\in\Sigma})$ and $(\mu,(\psi_f)_{f\in\Sigma})$ are the same morphism iff
$$ \mathfrak B \vDash \forall \vec x: \phi_f(\vec x)\leftrightarrow \psi_f(\vec x)$$
in order to get a definition of composition that's not too arbitrary.
