In my opinion, this is the most powerful and beautiful notes application I've ever seen. The last stable version is 18.104.22.168 for KDE3, but a port is in the works for KDE4 too.
BasKet has so many features I can't think what to begin with. It allows notes to be taken on more than one column or free choice, which means you can put each note wherever you want in the workspace. It allows tags, custom tags, global shortcuts, export to HTML, import notes from text files, Tomboy or KNotes. You can even insert images, links or launchers inside notes. You can backup all the baskets containing notes in a single, compressed file.
The main feature BasKet have though is its approach towards taking notes. It's not just a simple notes application which you'll use just to write down a quote or some short command or tutorial you've bumped into on the web, but it allows you to create and organise entire projects with text and images, put them in different, hierarchic baskets, and eventually export everything to an HTML file. I think this is great about BasKet, and it's definitely the most powerful notes-taking application, no matter what desktop environment one uses.
The current version doesn't allow printing of notes (except for exporting to HTML, and then printing it with a web browser eventually), but this is a feature which is to be implemented in the KDE4 port.
Tomboy is a GNOME notes application which offers pretty much anything you will need if you are a GNOME user: it allows you to search through notes, it supports text formatting like bold, italic, strikeout, highlighting, different font sizes. Tomboy also comes with a spell-checker, global shortcuts and several add-ons.
To mention a few plugins (called 'add-ins' in Tomboy): Export to HTML, Insert Timestamp, SSH Sync Service.
This is a lightweight notes-taking application which comes by default with KDE (included in the kdepim package) and works on the principle of 'sticking' the notes on the desktop. It offers less features than either BasKet or Tomboy, but it looks nice and it's useful for those who only want to take plain text notes in a fast manner, without the need to run a more heavy application on resources.
You can select the text and background colours, insert current date, set alarm, print or mail notes.
Homepage (deprecated, also see the Kontact homepage)
As a conclusion, I think the most powerful and fully-featured is BasKet, which can be used for large projects too, not only for notes. You can write entire essays, books or other projects with BasKet, and it will all look wonderful. I recommend Tomboy to those who use GNOME and prefer GTK applications over KDE/Qt ones, while KNotes is small but fast.