Let's start with the problem of deciding whether a given algebra-with-involution $(A,\ast)$ is cellular. The base-free characterisation of cellularity in terms of ideals shows that it is sufficient to (recursively) check whether there exists a cell ideal.
Just for completeness sake this is the definition:
Definition: Given an algebra-with-involution $(A,{}^\ast)$, a twosided ideal $J\trianglelefteq A$ is a cell ideal iff there exists a left-ideal $\Delta\subseteq J$ and a $A$-$A$-bimodule isomorphism $\alpha: \Delta \otimes_K \Delta^\ast \to J$ that is compatible with ${}^\ast$ in the sense that $\alpha(x\otimes y^\ast)^\ast = \alpha(y\otimes x^\ast)$.
Over field, we have the following characterisation of cell ideals:
Lemma 1: If $(A,{}^\ast)$ is an algebra-with-involution and $J\trianglelefteq A$ is a cell-ideal, then one of the following two cases happens:
There exists an idempotent $e$ s.t. $J=AeA$, $eAe=K\cdot e$ and multiplication is an isomorphism $Ae\otimes_k eA \to J$ of $A$-$A$-bimodules. If $char(K)\neq 2$, then $e$ can be chosen to be ${}^\ast$-invariant.
$J^2=0$
I'm going to be lazy here and assume that your are not in characteristic two.
Note that given an ${}^\ast$-invariant idempotent $e$, $AeA$ is a cell-ideal iff multiplication $Ae \otimes eA \twoheadrightarrow AeA$ is a bijection, because then $\Delta:=Ae$ is the left ideal required in the definition, $\Delta^\ast = eA$ and multiplication is automatically compatible with ${}^\ast$.
This leads us to:
Algorithm A1: Deciding for a ${}^\ast$-invariant idempotent $e$ whether or not $AeA$ is a cell-ideal.
Calculate the dimensions $n :=\dim_k Ae$ and $m := \dim_K AeA$.
$AeA$ is a cell-ideal iff $m=n^2$.
Now note that we only need to check one representative of every conjugacy class of idempotents, because conjugated idempotents generate the same twosided ideal.
EDIT 2018-07-20 Moreover observe that only the $Aut(A)$-conjugation class of $\ast$ is important when deciding cellularity of $(A,\ast)$, because $0=J_0<J_1<J_2<\ldots<J_k=A$ is a cellular chain for $(A,\ast)$ iff $0=\alpha(J_0)<\alpha(J_1)<\ldots<\alpha(J_k)=A$ is a cellular chain for $(A,\alpha\circ\ast\circ\alpha^{-1})$.
We use the following lemma to reduce the number of relevant quivers, relations and involutions dramatically:
Lemma 2: If $(A,\ast)$ is cellular and $A=KQ/I$ is a quiver-algebra, up to conjugation by some inner automorphism, $\ast$ comes from an involution on the quiver which fixes the vertices. In particular, $Q$ is symmetric, i.e. for all $u,v\in Q_0$ there are exactly as many edges $u\to v$ as there are $v\to u$ and $\ast$ exchanges them.
Proof: First we show by induction over $\dim_K A$ that $\ast$ acts as the identity on $A/rad(A) = \prod_{v\in Q_0} Ke_v$.
Let $J$ be a cell-ideal. If $J$ is nilpotent, then $J\subseteq rad(A)$. Then $A/J$ is again a quiver-algebra $A/J=KQ'/I'$ where $Q'$ has the same number of vertices, but potentially fewer edges. If $J$ is not nilpotent, it is of the form $AeA$ with some $\ast$-invariant idempotent $e$ by Lemma 1. In $A/rad(A)$ this idempotent $e$ must the equal to one of the $e_v$. Since lifts are unique up to conjugation, $e_v$ is conjugated to some $\ast$-invariant idempotent so that $\ast$ fixes $e_v$ under the action on $A/rad(A)$.
$A/AeA$ is again a quiver-algebra $A/J=KQ''/I''$ with $Q''$ having exactly one vertex less then $Q$ (namely $v$). By induction, $\ast$ act as the identity on $A/rad(A)$ in both cases.
We can now assume that that every vertex idempotent $e_v$ is conjugated to some $\ast$-invariant idempotent $e_v'$, say $e_v' = s_v e_v s_v^{-1}$. Then $s:=\sum_v e_v' s_v e_v$ is an invertible element ($s^{-1} = \sum_v e_v s_v^{-1} e_v'$) such that $s e_v s^{-1} = e_v'$. Therefore the vertex idempotents are invariant under some twist of $\ast$ with some inner automorphism.
Wlog we assume that the vertices themselves are invariant. Then $e_v (rad(A) /rad^2(A)) e_u \cong e_u (rad(A)/rad^2(A)) e_v$ as $K$-vector spaces via $\ast$ so that $Q$ is a symmetric quiver and by choosing an appropriate basis of $rad(A)/rad^2(A)$ we can assume that $\ast$ permutes the edges of the quiver. QED.
This lemma therefore shows that only finitely many involutions need to be checked. In particular, if $Q$ does not contain looped edges $v\to v$, then there is at most one relevant involution on $Q$ and exactly one iff $Q$ is symmetric.
Corollary 3: If $Ae_v A$ is a cell ideal, then for all pairs of opposite edges $v \overset{\alpha}{\underset{\beta}{\leftrightarrows}} u$, the loop $\beta\alpha$ is non-zero, but the loop $\alpha\beta$ is zero. In particular at most one of two adjacent vertices can give us an idempotent cell ideal.
Proof: $\alpha\in e_v A$ and $\beta\in Ae_v$ so that $\beta\alpha$ is the image of $0\neq \beta\otimes\alpha \in Ae_v \otimes_K e_v A$ and therefore non-zero in $A$. On the other hand, $\alpha\beta \in e_v A e_v = Ke_v$ so that $\alpha\beta - \lambda e_v \in I$ for some $\lambda\in K$. Now $\lambda$ must be zero because $I$ is contained in the ideal spanned by paths of length $\geq 2$. QED.
Also note that a quiver involution extends to an involution on $KQ$ so that the relation ideal $I$ must be $\ast$-invariant. This is another necessary criterion for cellularity.
Applying algorithm 1 recursively we can at least decide whether $(A,\ast)$ is both cellular and quasi-hereditary (which happens exactly iff only case 1 of lemma 1 occurs).
We still have to deal with the nilpotent case. To me this seems much more involved, because the structure of nilpotent cell ideals can be almost arbitrary. For every finite-dimensional left $A$-module $\Delta$ one can turn $A\oplus(\Delta\otimes\Delta^\ast)$ into an algebra such that $\Delta\otimes\Delta^\ast$ becomes a nilpotent cell ideal.
Of course, in principle the problem is decidable if you're working with finite fields, but the naive approach of enumerating all ideals will be hopelessly inefficient as we have seen previously. I'm going to continue thinking about it.
EDIT 2018-07-20:
Since we can assume that the vertex idempotents are $\ast$-invariant by Lemma 2, we can restrict the dimension vectors for any cell potential module $\Delta$ such that $J \cong \Delta \otimes \Delta^\ast$ is a nilpotent cell ideal, namely if $(d_1,\ldots,d_n)$ is the dimension vector of $\Delta$, then $d_i d_j = \dim e_i J e_j \leq \dim e_i rad(A) e_j$. In particular $d_i=\sqrt{\dim e_i J e_i} \leq \sqrt{\dim e_i rad(A) e_i}$. Note that the dimension matrix $(\dim e_i J e_j)_{i,j}$ is symmetric, of rank $1$ (when viewed as a matrix over $\mathbb{Q}$).
More precisely: Given any cellular chain $0=J_0<J_1<\ldots<J_m=A$ with associated cell modules $\Delta_k$, the dimension vectors $d_k\in\mathbb{N}^n \setminus \{0\}$ have the property that $C$ the Cartan-matrix is equal to $\sum_k d_k d_k^T$. Moreover these vectors are linearly independent over $\mathbb{Q}$. It is therefore possible to enumerate all combinations once one knows the Cartan matrix.
