Note-taking software like "Notational Velocity" for Linux
NVpy is "a cross-platform simplenote-syncing note-taking app inspired by Notational Velocity."
Looking at screenshots NVpy looks like a closer match than TomBoy.
Here's a little write-up of NVpy on Lifehacker.
Though this guy didn't like it and tweaked gvim a bit instead.
Looking more, I found NVVim which "is a clone of the mac app Notational Velocity in vim. It is designed for fast plain-text note-taking and retrieval."
TomBoy is a note taking application for linux, which is probably the closest thing to Notational Velocity currently available.