The main difference is that the relational database uses one instance only for every given entry. A 'flat file' system keeps repeating relational data all the time.
Example: if you have a customers database, each customer has a zip code. Right? Why not store those zip codes, unique values, in a separate table toghether with zip code area names, like 'Washington DC'. Now for each customer you only store the zip code, not the location. That way several customers that has the same zip-code will have a lookup on that number to put in the adress field. That is a relational database.
A non relational dtatabase, on the other hand, does not do this. Here the zip code and the name of where that zip code goes are stored in each and every entry.
The latter, can therfore, have same zip-codes and different adresses. Not so good in this case.
Are all databases relational? The answer is NO, and not all relational databases are built on the client/server paradigm. But most of the time you'll want a relational database server, so it's important to clarify the distinction.
A relational database manipulates only tables and the result of all operations are also tables. The tables are sets, which are themselves sets of rows and columns. You can view the database itself as a set of tables. A DBF file is not a relational database. You do not manipulate a DBF table as a set (you are always following an index) and you do not perform operation on tables that yield other tables as the result (you are just looping through records from one or more tables, even when you use the "SET RELATION" dBase statement).
Whereas MDB file is a relational database. though you can open and manipulate a MDB file just like a DBF file, navigating through records and index, you can also perform all operations through a relational view of the database and using SQL statements.
As per stats, most non-relational databases are based on some "navigational" model: an hierarchy, a linked list, a B-Tree, etc. It's common to refer to these as ISAM (Indexed Sequential Access Method) Databases. What is a database server? It is a specialized process that manages the database itself. The applications are clients to the database server and they never manipulates the database directly, but only make requests for the server to perform these operations.
So you can allow the server to add many sophisticated features, such as transaction processing, recovery, backup, access control and etc without increasing the complexity of every application. The server also reduces the risk of data file corruption, if only because only the server writes to the database (a crash on any client machine will not leave unflushed buffers).
A nice database server also takes advantage of the client/server architecture to lower network usage. If you open a DBF or MDB file stored on a file server you need to retrieve every record just to filter out which ones you really need. But if you connect to a database server, it filters out the unneeded records and send to the client only the data that really matters.
Access is a relational database but it is not a database server. mSQL, SQL Anywhere, DB2, Oracle are both relational databases and database servers. The Btrieve NLM is a database server but it is not a relational database.