Paper notebooks for me too. I like little bound ones that I can fit in a jacket pocket.

If I look at what notes I can still access after 1, 10, or even 20 years, it's all paper.

I love Freemind too. I use it for the "what do we know about this thing" phase of problem solving.