Update: Read an updated reference of 12 notes applications here.
Tomboy is a feature-rich notes application for GNOME with support for spell-checking, links, font style and size, bullet lists, global shortcuts, and plugins. Tomboy will also let you search notes and export them to HTML. The plugins (called add-ins in Tomboy) include exporting to HTML, backlinks to see what other notes link to the current note, Evolution Mail integration, printing support, local directory synchronization.
This is one of my favorite KDE applications. BasKet is called by some a killer application for Linux, due to its completeness regarding features and a different approach compared to other notes applications. BasKet organizes your notes in one or two columns, but it also allows to make them float around in the workspace. It supports inserting images, links, URIs to local files, tag notes, use priority colors, import/export, backup and restore notes, and much, much more.
According to the homepage, Zim brings the concept of a Wiki to your desktop. Written in Python with GTK bindings, Zim saves the notes as Wiki text and besides font styling and coloring features it also offers an autosave feature which allow to edit several notes at once without the need to worry about saving them. Zim allows you to insert images and symbols in the notes and comes bundled with several plugins (for most of them you will need additional dependencies). Among plugins there is GNU Plot integration, equations, diagramas, spell-checker, tray icon integration.
GNOME Sticky Notes
GNOME Sticky Notes is a simplistic application which can be added to the panel as a widget, and allows you to “stick” notes on your desktop. Among the basic features it offers are notes colors and background color, change the font size or sticking notes to all available workspaces.
KDE Notes Widget
This is just GNOME Sticky Notes, only for KDE. It allows configurable font sizes and colors, global keyboard shortcut and spellchecking.
I could also mention here NoteCase Pro, a commercial application with lots of features. The open-source version, although discontinued in 2008, is still available to download here. In Debian/Ubuntu, you can download the i386 DEB and install it by typing dpkg -i notecase_1.9.8_i386.deb as root in a terminal.