Error: gdal-config not found while installing R dependent packages whereas gdal is installed

In Ubuntu 18.04

I fixed this by sudo apt install libgdal-dev Hope someone find this helpful. Some above answers seems to be outdated and lengthy.

In earlier versions (which had apt-get)

sudo apt-get install libgdal-dev

You need the -dev package with headers and shared library links for development besides the normal package for deployment. Two different use cases as far as the distro is concerned.

On my distribution:

edd@max:/tmp$ dpkg -l | grep gdal | cut -c-72
ii  libgdal1-1.7.0                                1.7.3-6ubuntu3        
ii  libgdal1-dev                                  1.7.3-6ubuntu3        
edd@max:/tmp$ 

and R CMD INSTALL rgdal_0.7-8.tar.gz works just fine as you would expect from a CRAN package given all the build-time checks at CRAN.

Update late 2016: As @JoshO'Brien points out in the comment

Minor update: Here in 2016, running Ubuntu 14.04.2, libgdal1h seems to have replaced libgdal1(though libgdal1-dev is still needed). At least I get an error to that effect when I attempted to apt-get install libgdal1

For Ubuntu 16.04 the corresponding line would be
sudo apt-get install libgdal1i

Such renaming of upstream libraries is common; something such as apt-cache search libgdal can help locate the current package names. The important key though is that the "abstract" development package libgdal-dev is all that is needed to build as it pulls the "concrete" current run-time package (here: libgdal1i) in via a dependency.

You can use apt-file package, to find which package contains the missing file you are looking for.

First install the apt-file using the command apt-get install apt-file
Update apt-file using the command apt-file update
Now you can use apt-file to find the missing file. apt-file search gdal-config

For my case, I got the same error when configuring grass-7.1 from svn. As shown below:

    $ ./configure
    ...more...
    checking whether to use GDAL... yes
    checking for gdal-config... /usr/bin/gdal-config
                  ...more....
    ./configure: 1: ./configure: /usr/bin/gdal-config: not found
    ./configure: 6093: test: =: unexpected operator
    configure: error: *** Unable to locate GDAL library.

But, after looking for gdal-config file with apt-file as shown below, I was able to resolve the error, after installing the package libgdal1-dev

$ apt-file search gdal-config

Results

libgdal1-dev: /usr/bin/gdal-config

So I installed libgdal1-dev, as shown below:

$ sudo apt-get install libgdal1-dev