From Fedora Project Wiki

< QA

Exploratory testing is an approach to software testing that is not scripted or planned in as much detail as a more traditional test plan. Rather than walking through a series of pre-defined test cases, the tester is asked to think about the high-level test areas in the software. From there, the tester is encouraged to use their knowledge of the product and the code in order to navigate through different areas of the software. As they walk through the software, their emphasis is to find bugs, expose new test areas, and learn more about the product to help guide future test efforts.

The simplest definition from Exploratory Testing Explained by James Bach works the best:

Exploratory testing is simultaneous learning, test design, and test execution.

For further reading on exploratory testing can be found at http://en.wikipedia.org/wiki/Exploratory_testing.