Lotus Notes stores all data in NSF files. An NSF file is a container for Notes Documents, which are unstructured records. Each Document can have any number of Items in it, similar to that of a relational database's tables and columns. Unlike relational databases, however, there are no constraints at the data model level on what Items a Document must have, so each individual Document might contain vastly different data inside.
Notes Views are used to see the data inside Documents, usually filtering on Documents with similar Items. Notes Agents, Pages, and more tools are available to get the data out of an NSF easily.
Notes' strengths are its ease of capturing data via Forms, and outputing data via Views, XML, HTML, Java Servlets, etc. It manages distributed data easily via a powerful replication system. It is also highly touted for its built in security.
CouchDB, created by an ex-Iris/Lotus/IBM employee, Damien Katz, has many of those same strengths, without the overhead and cost of Lotus Notes.
The word document can cause confusion in the Lotus Notes world. File documents such as PDFs, Word docs, Excel files, etc are stored within Lotus Notes Documents as part of the unstructured data.
SharePoint stores data in SQL server. It's data is very list-based with the additional ability to store file documents on the server and maintain meta-information on them as well.
A SharePoint list is much like a flat table, but unlike Lotus Notes, that list does have constraints on its data.
SharePoint data is collected and exposed mostly via its Web-based interface, but there are mnay ways to access the data such as the SharePoint API, Web services, XML, and even directly from the SQL server (not recommended).
Usability: For end users, both rank high here. SharePoint is all Web-based and end-users can easily manage a SharePoint site themselves with little training. Lotus Notes requires a Notes client or requires a Domino application to be built for exposure via the Web. For developers, Notes is easier to use but is quirky and uses proprietary languages - the Notes Formula language and LotusScript. SharePoint requires no coding at all for some basic workflows and site manipulation, but to get serious control you need to be a .NET developer and the code can be very complex.
Retrieval performance: For small projects, Lotus Notes does very well. Very large databases with over 10,000 Documents tend to start to decline in performance. SharePoint uses SQL server so it can easily handle very large numbers of lists or files within its data store.
Search performance/quality: Both have good search capabilities, but SharePoint wins if you are trying to search a large number of documents.
Extensability/ integration: SharePoint is the more extensible. Both, however, can integrate easily with other systems using XML. Notes can also integrate using Java agents/servlets, and Web Services. SharePoint has its Web services API and third-party add-ons for integration.
Bonus: Lotus Notes just isn't as popular as SharePoint at the moment. There are key places for documentation such as www.notes.net, and various developer blogs.