There are various definitions of Diophantine equation, not all equivalent. But one standard definition goes as follows. Let $P(x_1,x_2,\dots,x_k)$ be a polynomial with integer coefficients. A solution of the Diophantine equation $P(x_1,x_2,\dots,x_k)=0$ is a $k$-tuple $(x_1,x_2,\dots,x_k)$ of integers that satisfies the equation. An equation is Diophantine partly because of its shape, but much more because of the kinds of solutions we are looking for.
General Diophantine equations can be exceedingly difficult. However, in principle one variable equation are simple. We have a polynomial $P(x)$ with integer coefficients. Let
Without loss of generality we may assume that the constant term $a_n$ is not equal to $0$. It is straightforward to show that any integer solution of the equation $P(x)=0$ must divide the constant term $a_n$.
So there is a simple (in principle!) algorithm for finding all the integer solutions of $P(x)=0$:
(i) Find all the divisors (positive and negative) of the constant term and then
(ii) Find out, by substitution, which ones of these divisors "work."
As you know, factorization of large numbers can be computationally difficult. However, there certainly is an algorithm for factoring.
Remark: There is a very famous related problem, called Hilbert's 10th Problem. Hilbert asked for a general algorithm that would, for any polynomial $P$ with integer coefficients, and possibly many variables, determine whether the equation $P=0$ has integer solutions. After earlier progress by a number of people, Matijasevich showed that there is no general algorithm of the type that Hilbert asked for. But as we noted in our answer to your question, there certainly is an algorithm that works for polynomials in one variable.
Diophantus himself in his Arithmetica looked mainly for rational solutions. Often, a problem is called Diophantine if we are interested in solutions that are somehow fairly closely related to the integers.
Note that (at least to people in Logic) the famous Fermat equation $x^n+y^n=z^n$ is not a Diophantine equation, since the exponents are also variable. Such equations are sometimes called exponential Diophantine, or, more casually, Diophantine.
A simple example: Consider the equation $3x^4-12x^3-x^2+4x=0$. We want to find all integer solutions of this equation. First rewrite our equation as
$x(3x^3-12x^2-x+4)=0$. This has the obvious solution $x=0$. Any other solutions must be solutions of the equation
By the result mentioned in the main post, any integer solution of this equation must divide the constant term $4$. The divisors of $4$ are $\pm 1$, $\pm 2$, and $\pm 4$. Substitute these values in turn for $x$. We find that $x=4$ is a root, but none of the others are. So we have found all the integer solutions of our original equation: they are $x=0$ and $x=4$.