NoSQL is more evolutionary than revolutionary. It essentially combines the existing ideas of "external database storage" with "using familiar data structures, not relational tables."
There are more types of databases than relational, for example hierarchical databases. While archaic by today's standards, it meshed really well with the data structures of its data (e.g. COBOL records). The point is, the data in the database was modeled closely to how records were laid out in the programming languages that used them.
Fast forward to the invention of relational databases, where finally the database separated concerns and, when properly normalized, is a great way to visualize most types of data and relationships between data. It is really easy to understand compared to other types of databases. What it utterly fails at, however, is storing data in a way that mirrors objects and classes in a program. Hence, the invention of object-relational mapping. In other words, the design of the database is actually a hindrance to the design of the program that uses it, which is why we need ORM libraries such as Hibernate. While clean and consistent, there is always that nagging doubt in the back of my mind that something is not quite right there.
This gave rise to two more types of databases, object databases and NoSQL.
Both attempt to solve the issues introduced by relational databases while not exposing us to the mind-bending horrors of hierarchical databases. Data is still laid out in repositories that vaguely resemble tables, but in actuality are more like programming data structures than relational tables. While object databases follow mostly well-defined rules, my understanding is that NoSQL is rather arbitrary. For example, a table might be visualized as a hash table or an array. There is not an easy, well-defined way to query them using an arbitrary tool analogous to Oracle SQL Developer or SQL Server Management Studio.
The idea is that one may define data structures that are easily searched in code, rather than piecing together SQL queries that are better-suited to a SQL database engine rather than expressing the query one desires. For example, fuzzy or partial matches are more difficult and perform worse in a relational database, while a NoSQL database may have a structure that is optimized for such a search and completes in a fraction of the time.
There are languages for querying NoSQL. However, there is no universal language such as what SQL is for relational databases.
While I am familiar enough with NoSQL databases, this question was the impetus for me to buy a quality book on the topic and to start reading it with the eventual goal of being a real expert on the topic. The remaining comments are based on NoSQL Distilled: a Brief Guide to the Emerging World of Polyglot Persistence by Pramod Sadalage and Martin Fowler.
The authors state that relational databases do not scale well to clusters capable of serving the data needed for sites such as Amazon and Google: NoSQL was developed to fit this niche, relaxing the concurrency and durability in ACID in order to server large number of queries that largely use static data (hence, ACID transactions are not as important).
Furthermore, they posit that NoSQL databases operate without a schema (page 10) which allows NoSQL databases to modify the structure of data more easily. I am not sure that the presence or absence of a formal schema matters in this regard, since SQL databases allow modifying schemas as well. Regardless, the two renowned authors make the claim so it is worth examining.
I believe that both of these main points serve only to enforce my primary point that NoSQL is evolutionary, not revolutionary. They still store data, and make incremental improvements to the scale and modifiability. They also make the point that NoSQL does not seek to usurp relational databases as the king of data storage, only to provide an alternative means of data storage for the types of data that need to scale and morph in a way that (they believe) relational databases do not support well enough.