What is Cordova, and how does it relate to PhoneGap?

PhoneGap was an open source project started by a company called Nitobi. As part of Nitobi's purchase by Adobe, because the PhoneGap project had many contributors from large companies like IBM etc, the project was contributed to the Apache Software Foundation.

At first the name was changed to "Callback", but then was renamed to "Cordova" (after the street the Nitobi offices were on at some point). This is because unlike the project itself, the name PhoneGap is part of Adobe's purchase of Nitobi.

Actually... as Brian Leroux put it himself: "PhoneGap is powered by Cordova. Think: webkit to safari."

http://blogs.nitobi.com/andre/index.php/2011/10/03/nitobi-enters-into-acquisition-agreement-with-adobe/

As for the GitHub project linked to in @TDeBailleul's answer, I suspect that nostalgia over the street name led Brian to name one of his projects "Cordova", however, that "Cordova" has not been updated in 9 months and is not the Apache Software Foundation incubator project "Cordova".

http://incubator.apache.org/projects/callback.html

The brand new shiny Cordova web page is up now and may shine even more light on the subject.

http://incubator.apache.org/cordova/

Update: In the time since I posted this answer, some things have changed and there are actually some differences now, mostly around the CLI Tooling.

So I wrote and update: http://blog.devgeeks.org/post/73789983750/cordova-vs-phonegap-an-update

here a blog post that explain how both phonegap and cordova are here to stay: PhoneGap, Cordova, and what’s in a name?

From https://github.com/brianleroux/cordova README.md

A PhoneGap project toolchain that automates common tasks for building cross platform mobile projects with OS X.

Automate common development workflow tasks such as: compiling, debugging, testing, releasing and other things in between. As an added benefit projects generated with Cordova create a consistent, predictable, easy to understand and therefor extend software project. A number of conventions are introduced removing the need for mobile developers to relearn their tools or, worse, rebuild them for every project.

PhoneGap and Cordova are not the same, Cordova is a toolchain that enhances PhoneGap project developments