When you add an IMAP-based email account (including MobileMe and Gmail) to iPhone 4, in addition to the previous options you now get a toggle for "Sync Notes".
Apple's desktop Mail client includes special folders that serve as repositories for notes, so perhaps this is now (finally) being echoed on the iPhone.
Whether or not this gets tied in to the actual Notes app remains unknown (it doesn't seem to right now, but it may just not be working yet). It also doesn't seem to be an option for Exchange accounts (yet?).
If you discover anything else about iPhone 4 Notes sync, let us know!
[Thanks anon for the tip!]