In effect you're asking whether a given power series $y(x) = \sum_{n=0}^\infty a_n x^n$ satisfies a quadratic equation $a(x) y^2 + b(x) y + c(x) = 0$ with $a,b,c$ polynomials of low degree in $x$, say degree less than $\delta$. This is a linear system in $3\delta$ variables (the coefficients of $a,b,c$), so it's easy to test whether it has a nontrivial solution; and once you have several more than $3\delta$ coefficients of $y$ your linear system has several more equations than unknowns so the existence of a nontrivial solution is strong evidence that you've found the correct formula for $y$.

In the case of the Catalan numbers, if we take $\delta=2$ we're looking for a linear dependence among the sequences of coefficients of $1,x,y,xy,y^2,xy^2$, which are respectively

1, 0, 0, 0, 0, 0, 0, 0, 0, 0, ...

0, 1, 0, 0, 0, 0, 0, 0, 0, 0, ...

1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, ...

0, 1, 1, 2, 5, 14, 42, 132, 429, 1430, ...

1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, ...

0, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, ...

and in this simple case you'll find the linear relation $1 - y + xy^2 = 0$ "by inspection", but in any case a linear algebra package will find the corresponding dependence $(1, 0, -1, 0, 0, 1)$ automatically. Presumably that's what's done at some level by the **seriestoalg** routine that Richard Stanley recommends.

Naturally this idea works for finding dependencies whose degree in $y$, call it $d$, exceeds 2; for instance you can find a cubic over ${\bf Q}(x)$ satisfied by the generating function with $a_n = (3n)! / (n! (2n+1)!)$. [The proof is a standard exercise in residue calculus; for two elementary alternatives see my "one-page papers" at http://www.math.harvard.edu/~elkies/Misc/catalan.pdf and http://www.math.harvard.edu/~elkies/Misc/catalan2.pdf .]

For large $\delta$ there are algorithms for finding such relations that are more efficient than generic linear algebra, analogous to (but simpler than) the lattice reduction that's used for finding integer relations among real numbers known to some accuracy. I don't know if such an algorithm is implemented in **seriestoalg** or in another available package.