TUAW reports on the first native Instant Messaging client for the iPhone.
The application is called Apollo IM and only provides support for AIM accounts at this time and is described as an "early beta" release.
With all native 3rd party iPhone applications, you need to use various tools/hacks to get the applications loaded. Doing so also may require you to restore your iPhone before upgrading to the newest versions of iPhone updates.
A direct download (.zip) is available, or can also be installed via Installer.app.