It should be clear that one (and only one) of the elements is the identity element of your respective tables, and that an isomorphism must map these elements to each other. So the question remains, what can we deduce from the remaining three elements?
You are correct that IF the two groups are isomorphic, that the mapping between them must be a bijection on $\{a,b,c\}$. Fortunately for you, there are only six such mappings:
The identity map (if they are not the same table, we can rule this out),
Three transpositions: swap $(a,b)$, swap $(a,c)$ or swap $(b,c)$
Two "cyclical" maps: $a \to b \to c \to a\dots$ ,
$a \to c \to b \to a\dots$
But there is a faster way: deduce how many elements $x$ have the property that:
$x\ast x = e$ (this amounts to finding out how many times $e$ (or its analogue) occurs on the diagonal of the table).
This is the same as counting the number of elements of order $2$.
While having the same number of elements of order $2$ does not guarantee two groups are isomorphic; what is true, is that having differing numbers of elements of order $2$ proves two groups are not isomorphic. This is something worth remembering, as it often proves to be a useful short-cut.
And in the special case of groups of order $4$, it indeed settles the matter (because $4$ has a limited set of divisors, being a prime power).
If your two tables have the same number of elements of order $2$, and they are indeed group tables (it turns out showing associativity is "hard" from just the table information), they will be isomorphic. But I caution you here, the isomorphism between them will not be unique, in fact you should be able to find at least two such permutations (bijections) of $\{a,b,c\}$ that will work.
This underscores one of the inherent difficulties with Cayley tables: it is possible to have several distinct tables that represent "the same" (that is, isomorphic) group. One kind of group of order $4$ can have six tables, the other kind can have two. So in this sense Cayley tables are "inefficient conductors of information".
If we list the orders of the respective elements, there are only two lists (when ordered in increasing order):
$\{1,2,2,2\}$
$\{1,2,4,4\}$
It turns out for groups of order $4$ (but the proof of this is too long for this post) that this is all there is, and that any two groups of order $4$ of the same "order type" are isomorphic. I would recommend you try to prove this for yourself, it's interesting.
If the two groups are of the first order type, any permutation of $(a,b,c)$ yields an isomorphism. If the two groups are of the second type, there are only two possibilities, the identity, or a swap of the two elements of order $4$ (assuming you use the same "alphabet" for your two tables).
By TDLC: I mean totally disconnected locally compact group. Consider the conditions, for $G,H$ discrete groups:
(1) there exists a TDLC group $M$ admitting $G,H$ as subgroups, with a compact open subgroup $K$ such that $K\cap G=K\cap H=\{1\}$ and $GK=HK=M$.
(2) $G$ and $H$ are both cocompact lattices, with the same covolume in some common TDLC group;
(3) $G$ and $H$ are both cocompact lattices in some common TDLC group;
(4) $G$ and $H$ are both cocompact lattices in some common locally compact group;
(5) $G$ and $H$ are quasi-isometric.
Then (1)$\Rightarrow$(2)$\Rightarrow$(3)$\Rightarrow$(4)$\Rightarrow$(5).
(for (1)$\Rightarrow$(2), use the automorphism group of the graph as TDLC group)
For $G,H$ finitely generated, (1) is equivalent to (1') $G,H$ admit actions on some common finite degree connected graph, that are simply transitive on the set of vertices, which, in turn, is equivalent to sharing some Cayley graph (Here Cayley graphs are assumed unlabeled, unoriented, with no multiple edges). For (1)$\Rightarrow$(1'), choose a bi-$K$-invariant symmetric subset $S$ of $G$ such that $K\backslash S/K$ is finite, which generates $G$, and use it to define a $G$-invariant graph (=incidence structure) on $G/K$, namely $gK-hK$ if $h\in gS$.
For finitely generated groups, none of the implications can be reversed.
Counterexample to (2)$\Rightarrow$(1): $\mathbf{Z}$ and $\mathbf{Z}\times\mathbf{Z}/2\mathbf{Z}$.
Counterexample to (3)$\Rightarrow$(2): the trivial group and $\mathbf{Z}/2\mathbf{Z}$ (there are infinite ones too).
Counterexample to (4)$\Rightarrow$(3): $\mathrm{Hei}(A)$ denoting the Heisenberg group over the ring $A$, $\mathrm{Hei}(\mathbf{Z}[\sqrt{2}])$ and $\mathrm{Hei}(\mathbf{Z}[\sqrt{3}])$.
Counterexample to (5)$\Rightarrow$(4): if $\Gamma$ is a cocompact lattice in $\mathrm{Sp}_4(\mathbf{R})$ and $\tilde{\Gamma}$ its inverse image in the universal covering, then $\Gamma\times\mathbf{Z}$ and $\tilde{\Gamma}$ are the examples. (Indeed (4) implies that $G$ has Kazhdan's Property T iff $H$ does, but $\tilde{\Gamma}$ has Kazhdan's Property T while $\Gamma\times\mathbf{Z}$. So they don't satisfy (4), while they are quasi-isometric, since they are commable, i.e. one passes from one to another by a chain of cocompact inclusions in both directions.)
Nevertheless, (non-)quasi-isometry already provides a strong obstruction to (1), and the various quasi-isometry invariants we have could be used to extend this chain of implications.
It is using (1) that I can see easily that $\mathbf{Z}$ and $\mathbf{Z}\times\mathbf{Z}/2\mathbf{Z}$ don't satisfy the criterion.
To directly see that $\mathbf{Z}$ and $D_\infty$ satisfy (1): take $M=D_\infty=\langle a,b\mid a^2=b^2=1\rangle$ as ambient group: it admits, as subgroup of index 2, the subgroups $\langle ab\rangle\simeq\mathbf{Z}$, and the subgroup $\langle a,bab\rangle\simeq D_\infty$, and the subgroup $\langle b\rangle$ then plays the role of $K$.
Note that in general, if $G$ and $H$ are subgroup of the same finite index in a common (finitely generated) group $M$, then they satisfy (2); however they may fail to satisfy (1).
Being quasi-isometric (or commable) is transitive. However, conditions from (1) to (4) are not transitive a priori, although I don't have a counterexample in mind for all of them at the moment. So it means that a priori it makes sense to make the same discussion for $n$ given groups.
At least (3) and (4) are not transitive, based on Proposition 19.83 in ArXiv/1212.2229: namely, take $p,q,p',q'$ be odd primes with $\{p,q\}\neq\{p',q'\}$. Let $G$ and $H$ be the (virtually free) free products $C_p\ast C_q$ and $C_{p'}\ast C_{q'}$. Then the pair $(G,H)$ fails to satisfy (4) (and hence fail (3)), by that proposition. However, if $n$ is large enough, the free group $F_{1+n!}$ is isomorphic to a finite index subgroup of both $G$ and $H$, and hence the pairs $(G,F_{1+n!})$ and $(F_{1+n!},H)$ both satisfy (3) and (4).
Best Answer
Proving that two groups are isomorphic is a provably hard problem, in the sense that the group isomorphism problem is undecidable. Thus there is literally no general algorithm for proving that two groups are isomorphic. To prove that two finite groups are isomorphic one can of course run through all possible maps between the two, but that's not fun in general.
For your particular example, there's not much to say. It depends on what you know about $D_4$. If you know a presentation of it, then you can prove that what you've defined is actually a homomorphism which is moreover surjective. Since the two groups have the same order, you're done.
For recognizing a finite group via a presentation you can sometimes use the Todd-Coxeter algorithm.