Any program designed to function on the base operating system for a computer, rather than being embedded from within another program; they were referring to the recently released Facebook app that can run on its own, not through the Safari web browser on the iPhone (as you know the iTunes App Store was opened on July 11th, with several hundred “native” iPhone apps released).
Sometimes also referred to as a “Standalone” application as well. Also mentioned in the other discussion, this site (http://Fluther.com) has a mobile version (http://i.fluther.com), but still relies on the Safari browser to run, so it is not (yet) a native app.