I love writing on the "Sustainable Earth" notebooks from Staples [1]. The only thing I dislike is that the pages are perforated so they tear more easily than I'd prefer in a long-term notebook.

At only a few dollars, I don't feel bad scribbling on one or two pages, and then tearing them out and re-writing them more neatly afterwards. The paper is made mainly of recycled sugar cane, and is an absolute joy to write on. They also sell printer paper of the same.

1: http://www.staples.com/sustainable+earth+notebook/directory_...?