How do I find the build dependencies of a package?

For a full list of dependencies, including the dependencies' dependencies, you can use:

apt-rdepends --build-depends openoffice.org

The command may remind you to install apt-rdepends first.

You can use the following command to only show the ones that are not installed:

apt-rdepends --build-depends --print-state openoffice.org | grep NotInstalled

See apt-rdepends --help for all the options.

Note: This will generate a massive list.
apt-rdepends -b xterm, for example, generates 8773 lines of output, and takes it's time doing it.

If you only want to see the packages that are required to build the topmost package, i.e. what do I need to install to build nautilus, run:

apt-rdepends --build-depends --follow=DEPENDS nautilus

This is roughly equivalent to Carsten Thiel's answer (The following NEW packages will be installed), but the output format is a bit nicer. It also only shows the topmost package, whereas simulated apt-get also shows packages installed as dependencies of those.

This also shows packages that are installed. But it may also show packages that are installed by default. Unfortunately, neither method is much help when you're trying to clean up your system after running apt-get build-dep. As far as I know, there isn't a reliable method of finding which ones were installed except from looking at the apt log file at /var/log/apt/history.log.

apt-cache showsrc <pkgname> | grep ^Build-Depends

showsrc displays the debian/control file for a given source package. We then grep for the line(s) which begin with 'Build-Depends' which has the list of packages needed to build from source.

The option -s (--simulate) will output everything that would be done without doing anything. You don't even need root privileges for that.

apt-get -s build-dep <package>