A relational database is a database constructed and used according to the principles set out in A Relational Model of Data for Large Shared Data Banks by E.F.Codd (in Communications of the ACM Volume 13 Issue 6, June 1970).
EMJ: That is really the only valid short definition. There are lots of definitions scattered around the internet, but they tend not to agree with one another, and very very many of them are wrong to some extent if not completely wrong.
Many things written about relational databases are really about Relational Database Management Systems or about Structured Query Language (SQL).
Relational databases are probably the most widely-used kind of database.
Relational databases are special in that the database itself supports "search with complex query" (can combine conditions with boolean operations, even using intermediate search results for additional queries), which simplifies parallelization and scaling to very large datasets.
EMJ: The above has been here since the second edit to this page in 2008, and is one of those things that is more properly about RDBMSs