My main problem is finding a suitable data storage system

Nahh ;-) Your main problem is figuring out what your note taking application should do. Once you've done that picking a storage mechanism should be obvious.

My advice would be to start with plain text files (and you'll be surprised how far you can go with plain text files :-). Keep a nice clear API between your application logic and your data store. As soon as you find you need something more sophisticated than plain text files use it. Swapping in a new persistence layer should be simple.

Let you application's requirements drive what the data store should be, not the other way around.

Also, have you considered using a wiki like CGI::Kwiki as your note taking program? Various wiki's have been doing the job for me for a year or so now - might be worth considering.