According to the rgdal package manual:
for building from source: GDAL >= 1.11.4, library from https://trac.osgeo.org/gdal/wiki/DownloadSource and PROJ.4 (proj >= 4.8.0) from https://download.osgeo.org/proj/; GDAL OSX frameworks built by William Kyngesburye at http://www.kyngchaos.com/ may be used for source installs on OSX. For installation with older external dependencies, override configure checks with --configure-args="enable-deprecated=yes". Consider source installations using archived versions of rgdal contemporary with installed external dependencies, for example, rgdal_0.8-7 for PROJ4 4.8.0 (March 2012).
If you are under Linux, you have to build a package from the source, and you will have to install the corresponding libraries on your system. If you are under Mint, Ubuntu or another Debian derivative, you can do :
$ sudo apt-get install libgdal1-dev libproj-dev
One tip that can be useful under a Debian system is to install the apt-file package and run :
$ sudo apt-file update
If you get an error such as :
configure: error: proj_api.h not found in standard or given locations.
You can use the following command to find which package you must install to get the missing file :
$ apt-file search proj_api.h libproj-dev: /usr/include/proj_api.h