As always with FFmpeg continuing development shifts the goal posts many times and this is certainly true of nvenc and FFmpeg. There have been 3 phases:

1. Roll your own: Pre August 27th 2016 it was necessary to track down your own headers to build nvenc. Arduous and more than a little confusing.
2. Built into the source: August 27th 2016 saw the required headers incorporated as part of the FFmpeg source, nothing required but the ability to compile the FFmpeg source from git, or use a 'release' version cut from git at this time.
3. Use nv-codec-headers: On February 26th 2018 the NVidia headers were removed from the FFmpeg source. A separate git repository was created to hold continuing work with these headers. At the moment these headers must be installed as well as FFmpeg from git to get access to nvenc and friends.

Two steps are required:

1. Install the nv-codec-headers package:

Something like the following Terminal commands should suffice:

sudo apt-get install make git
mkdir $HOME/nv-codec-headers_build && cd $HOME/nv-codec-headers_build
git clone https://git.videolan.org/git/ffmpeg/nv-codec-headers.git
cd nv-codec-headers
make && sudo make install

If for some reason you change your mind and wish to completely remove the installed files as well as the build directory simply run the following two Terminal commands:

sudo rm -v /usr/local/{lib/pkgconfig/ffnvcodec.pc,include/ffnvcodec/*.h}
rm -rfv $HOME/nv-codec-headers_build

And your system has been cleaned. If however you wish to continue use the following step:

2. Compile FFmpeg:

Use this very well tested guide:

• Compile FFmpeg on Ubuntu, Debian, or Mint
  https://trac.ffmpeg.org/wiki/CompilationGuide/Ubuntu

The nv-codec-headers will be automagically recognised (no extra ./configure options are needed) and nvenc will be successfully built.

Testing:

I have tested this on Bionic Beaver LTS and the results are:

andrew@ilium:~$ ffmpeg -encoders 2>/dev/null | grep nvenc
 V..... h264_nvenc           NVIDIA NVENC H.264 encoder (codec h264)
 V..... nvenc                NVIDIA NVENC H.264 encoder (codec h264)
 V..... nvenc_h264           NVIDIA NVENC H.264 encoder (codec h264)
 V..... nvenc_hevc           NVIDIA NVENC hevc encoder (codec hevc)
 V..... hevc_nvenc           NVIDIA NVENC hevc encoder (codec hevc)
andrew@ilium:~$

And if you see a similar picture as above, and you have a supported graphics card, you are right to go :)

Notes:

• The latest version corresponds to Video Codec SDK version 11.0.10 and requires NVidia drivers version 455.28 or newer.
• Older versions: There is now an automated github copy of the nv-codec-headers which also creates tarballs perfect for using an older version of the headers. Great if you want the headers to sync with an older version of the NVidia drivers that you are unable or unwilling to update.
• Hardware Acceleration Guide for FFmpeg: FFmpeg Wiki guide for hardware acceleration in general with FFmpeg, a canonical section for compiling and using nvenc...