UPDATE: For a more up-to-date list, check the new section NaNoWriMo Software Picks.
While it’s a Windows-only freeware, it can run fine on WINE.
You must add the following libraries so it can run without problems: riched20, riched32, and oleaut32. To do this you go to Applications > WINE > Configure WINE > Libraries tab or run it from the Terminal: winecfg
For outlining, I tried a bunch of programs, but I must say KnowIt wins. It’s a note-taking program that lets you organize your notes in a tree structure. This is very useful for basic things like outlines, character descriptions, etc.
GRAMPS Genealogy System
Another wonderful tool for character organization is the GRAMPS Genealogy System, which is a genealogy (family tree) software. If you want to have your characters’ families well organized, this is the program for you.
This one is like KnowIt on steroids. It offers a lot more customization than the previous. It lets you add media files (pictures, sounds, etc.) to your notes, you can assign colors to your notes, format the text, add backgrounds, etc. And you can export the final work as a HTML page.
This is great to add references and sources, character photos and things like that.
I haven’t tried Microsoft’s OneNote, but from what I’ve heard, this program is a good Linux alternative.