Suppose I have a hypersurface in $\mathbb{C}P^n$ given by some $f(z_1, \dots, z_{n+1}) = 0.$ Is there an algorithm which returns a rational parametrization if there is one, and "not rational" otherwise?

For smooth cubics in $\mathbb P^5$ this is unknown. That is, there are certain explicit families of such cubics that are known to be rational (those that admit a Pfaffian description, for example) but beyond these the problem of rationality for cubic $4$folds is a famous unsolved problem. 


Here is my attempt at a heuristic as to why the problem should be undecidable. Suppose we have a hypersurface $X$ of dimension $n$ and we wish to decide whether or not it is rational. I will assume that $n\geq2$. Then giving a rational map $\mathbb{P}^n \dashrightarrow X$ is the same as giving a $\mathbb{C}(t_1,\ldots,t_n)$vauled point on $X$. However, "Hilbert's 10th problem" for such function fields is undecidable (see http://www.math.psu.edu/eisentra/varieties.pdf). Hence the problem you have asked for is undecidable. Edit: As noted in the comments, this reasoning is not quite correct as for Hilbert's 10th problem we fix $m$ and a field $\mathbb{C}(t_1,\ldots,t_m)$, then allow the dimension $n$ to vary. Hence why it is only a heuristic! Note that for Hilbert's 10th problem, the case $\mathbb{C}(t)$ is still open. Edit: As remarked below, rationality for curves is decidable. One just needs to compute the genus of the normalisation of the projective closure of the curve. 

