Yes, the other computers must have Notezilla installed if you are using the "Send To Computer" option. However, if you use "Send To Contact" option, the recipient will get the Windows sticky note via email if he/she is not a Notezilla user.
If A wants to send note to B, then, you should add B to A's computer list. This opened the firewall on A. But we haven't opened the firewall on B. So add A to B's computer list too. Then try sending note to each other.
If the above doesn't work, try to give IP address as the computer name.
Sending notes to remote computer is not easily possible as the recipient computer, its network, router etc should allow it. So you must use 'Send to Contact' for remote computer. Please note that to Send to Contact, you need to create a Notezilla.Net account for both the sender as well as the recipient of the sticky note.
You can watch related videos on http://www.conceptworld.com/Notezilla/Videos to learn more.