What provides curses headers named curses.h?

You can install libncurses5-dev package via Software Center or:

sudo apt-get install libncurses5-dev

Also, you can install the package by clicking here.

When you need a file or package and can't find it you can use some tools.

1. apt-file

First, install apt-file and update it.

sudo apt-get install apt-file
apt-file update

You can search with apt-file needed files or packages.

apt-file search curses.h

2. Use packages.ubuntu.com

Go to this link.

On right top, select package contents if your are searching a file included with a package. If you need a package directly, just search it with its name choosing package names.

Find package from file

Edit: This only works for an installed package, so is not able to answer the question. Better is heartmagic's answer

To find out what package a file is part of, you can use

dpkg -S <file name>

For example, dpkg -S curses.h gives me this output:

libncurses5-dev: /usr/include/ncurses.h
libncurses5-dev: /usr/include/curses.h

Find files in package

Edit: You need to have the package installed for this to work.

To get the list of files provided by a package, use

 dpkg -L <package name>

For example dpkg -L libncurses5-dev gives me the following output

/.
/usr
/usr/include
/usr/include/curses.h
/usr/include/cursesapp.h
/usr/include/cursesf.h
/usr/include/cursesm.h
/usr/include/cursesp.h
/usr/include/cursesw.h
/usr/include/cursslk.h
/usr/include/eti.h
/usr/include/etip.h
/usr/include/form.h
/usr/include/menu.h
/usr/include/nc_tparm.h
/usr/include/ncurses_dll.h
/usr/include/panel.h
/usr/include/term.h
/usr/include/term_entry.h
/usr/include/termcap.h
/usr/include/tic.h
/usr/include/unctrl.h
/usr/lib
/usr/lib/libform.a
/usr/lib/libmenu.a
/usr/lib/libncurses++.a
/usr/lib/libncurses.a
/usr/lib/libpanel.a
/usr/lib/libtic.a
/usr/share
/usr/share/doc
/usr/share/doc/libncurses5-dev
/usr/share/doc/libncurses5-dev/copyright
/usr/share/doc/libncurses5-dev/changelog.Debian.gz
/usr/include/ncurses.h
/usr/lib/libncurses.so
/usr/lib/libtic.so
/usr/lib/libform.so
/usr/lib/libmenu.so
/usr/lib/libpanel.so
/usr/lib/libcurses.a
/usr/lib/libtermcap.a
/usr/lib/libtermcap.so
/usr/lib/libcurses.so

This includes directories as well.

Find ONLY files (not directories) in package

To get just the files the package contains:

dpkg -L libncurses5-dev | while read file; do if [[ -f $file ]]; then echo ${file}; fi; done

(Description: Get the provided files, and for each one, only print it if it is a file.)

More information

You might find this table useful. Just look at the first column (action) and third column (deb) to get a good overview of what you can do. (unless you are curious of course, then look at the other columns.)