This is a natural extension of test-driven-development, where one writes a computable test for each component in the software system before the component itself is written. The insight is that these tests are specification behaviors in the system so one can name them as such rather than as "tests".
The idea of building a model of the specification which can be computed is not new. There are strong similarities with Design by Contract (Meyer, 1986) and I am sure you can find older examples in the Lisp community with strong similarities. The BDD term is not defined rigorously, in tradition with most software development terms, sadly. Thus it means different things to different people. Some will say that DbC is BDD and some will say that it is not.
Main insight: If you have a specification written in English prose, you have no way to automatically check if the program lives up to the specification. You can only test it manually, which is a tedious, cumbersome process prone to failures. If the process is computable, we can get the machines to work for us and work out the details.
Getting the machine to understand the specification means it needs to be precisely specified, like a computer program. Our hope is that while the program specified may be complex, the specification itself is not. Thus we can specify the behavior of the program and have some assurance that the specification is correct. If the specifications are as hard to write as the main program it turns out to be turtles all the way down.
There are several ways we could attempt to write down a formal specification. We could, for instance, use Hoare logic - meaning we specify the behavior of the program in an assertion language different from the implementation language. One then tests the specification by verifying that the rules of HL is fulfilled.
Another path is to make the type system strong enough to capture formal logic and specify the program in the type system. To achieve this, one must have a type system much more expressive and powerful than what most mainstream programming languages provide. Testing the specification then amounts to a type check. Aside: Expressive type systems like the one found in Haskell or ML provides an approximation to this complete correctness. When we say that "type systems eliminate bugs in the program", we mean that the approximation caught a bug which would otherwise have slept into the program. Note that (static) type systems are a knob you can turn. The more expressive the system, the better an approximation to the specification. Turned to 11, the type system is the specification, but most programmers abhor the idea of programming at this level of precision. End of aside.
The BDD path is to define the specification in the host-language as a program itself. Usually this can be done by a compiler from a domain-specific language (describing behaviors) into the language in which the tested component is written. The advantage of this approach is that you don't need a separate tool chain but can reuse the existing one for running your tests. Testing the specification is done by running the spec-program against the implemented components and observing their behavior.
Thus, BDD is a runtime-oriented path to verifying the program specification. We check the program correctness by executing the test. I would imagine that we also design the behaviors such that they cover all paths of the component. This is fairly easily achieved by a coverage checker.
Personally, I see the BDD-idea as a poor-mans formal specification -- it is what you end up with if you just use the available tools rather than define a spec-language. You end up with exactly the same problems as most formal specifications any way: Explaining and understanding what they mean is hard. The problem can somewhat be alleviated by clever tricks where the actual code is hidden in a textual presentation which normal people would have a chance at understanding. This part of BDD circles around the problem of defining a good User Interface for the specification in question. This is the part of BDD I find the most interesting.
Also, the fine merits of BDD might be the first casualty to any deadline. Deadlines kill. Anything which can be placed into the scheme of "short-term good, long-term bad" and incurs technical debt is turned on as soon as the deadline approaches. Everything falls to a fast cost-benefit analysis. The problem here is that there are no measurable way to evaluate different software development methodologies so an equally good and faster analysis is thrown dice.