p4est is a library that manages meshes that are distributed across multiple processors. It forms the basis of deal.II's implementation of finite element solvers that can use meshes that are too large to be held on each processor individually.
You need to install p4est before deal.II. To do so, you can download it from here. You can either choose to manually compile and install p4est (as explained in documentation of p4est), or alternatively use a script that will automatically compile and install a debug and optimized version of p4est.
If you want to use the script, copy the tarball to a fresh directory together with the p4est-setup.sh script (the one from this link, not one you may have gotten from the p4est webpage). Then make the file executable and call the script as follows:
chmod u+x p4est-setup.sh
./p4est-setup.sh p4est-x-y-z.tar.gz /path/to/installation
where p4est-x-y-z.tar.gz is the name of the p4est
distribution file, and /path/to/installation is a
directory into which you want to install p4est.
In both cases, you can configure deal.II using a line like
cmake -DP4EST_DIR=/path/to/installation -DDEAL_II_WITH_P4EST=ON -DDEAL_II_WITH_MPI=ON <...>
if the p4est library isn't picked up automatically.