File Geodatabases (GDB) are a relatively new format compared to shapefiles, and they were created by Esri for their Arc product line. They allow the storage of multiple vector and raster layers in a single database. Some government agencies release data officially in this format. However, only in the last few years has it been possible to open this data with open source tools.
For this recipe, you will need a File Geodatabase, naturalearthsample.gdb.zip, which is included in the sample data, and GDAL 1.11 or a newer version.
Check your GDAL version by navigating to Help | About | About. If your GDAL is a lower number, upgrading your QGIS should get you a new enough version. Refer to http://qgis.org/en/site/forusers/download.html for more options, especially if on Linux where you may need third-party repositories for a newer version of GDAL.
File Geodatabases are actually folders full of all sorts of binary files. Typically, you will get them zipped and must extract the zip to a real system folder before you can use it.
naturalearthsample.gdb.zip file so that you have a folder called naturalearthsample.gdb.naturalearthsample.gdb folder (if you haven't unzipped this already you need to do this first).

This is fairly straightforward. You tell QGIS the root folder of the File Geodatabase, and it can figure out how to use all the files inside of the folder appropriately. As long as GDAL has a driver for a given format, then you should be able to open the data with QGIS. Support for additional formats is always ongoing and being refined.
The key limitation to File Geodatabase drivers currently are that raster layers are not supported and that there is limited write ability for vectors. There are actually two different drivers. One is an open source project, which is built by the community, and is the default driver. The other is based on a development library, which is released publicly by ESRI that has specific license restrictions.
OpenFileGDB, the open source community-built driver, can open multiple versions of GDB (9 and 10), is read only, and comes with most versions of GDAL 1.11+.
The ESRIFileGDB driver can read and write vector layers (this has some limitations, which are discussed in the link in the See also section). However, it often can only open the version of GDB it was built for (the newest version only reads newer GDB formats, for example, 10). Sometimes, it requires you to build the GDAL driver from the SDK code provided by ESRI. (This is done for Windows users as part of osgeo4w; Linux, and Mac users at this time need to compile GDAL with the FileGDB SDK 1.4.)
To use this driver, pick a different type in the dialog as ESRIFileGDB. If you don't see it listed, you don't have a version of GDAL that includes this, and you will need to compile GDAL yourself.
If you get a database in this format, consider batch converting it to Spatialite, which will maintain most of the same information and give you full read, write, query, and edit capabilities in QGIS. You'll need the ogr2ogr command for now until someone writes a plugin (or you could load them one by one with the DB Manager):
ogr2ogr -f SQLite naturalearthsample.sqlite naturalearthsample.gdb -skip-failures -nlt PROMOTE_TO_MULTI -dsco SPATIALITE=YES