CouchDB a real world example

Your application is quite easy to do with CouchDB. You would have a database per user. Contacts are simply documents in a particular user's database. CRUD is just talking to the database using HTTP. You could create views that emit keys (last name, first name) to allow for sorting.

For powerful search I would recommend couchdb-lucene.

IBM has a great tutorial, making use of curl to read/write via the REST interface.

The upcoming book by O'Reilly is free to read online: http://books.couchdb.org/relax/

Just install and play around - you can do straight http requests using curl on the command line, or use the built-in web interface called futon.

Storing and retrieving data is really easy, the hardest part is thinking in terms of map/reduce-views instead of sql queries.