Introduced in Windows Server 2003 as Application Experience Lookup Service, Application Experience is basically a database of third-party applications that have problems running properly on Vista. If Vista sees a program from this database, it will alter it’s behavior in some way (create a compatibility shim) to help the program run smoothly. This could be anything from redirecting a registry setting that’s trying to insert itself in the wrong location to assisting with window redraws.

If most of your programs are up-to-date and you aren’t experiencing any issues, you can disable this service without concern. Most people will probably be fine leaving it running as it doesn’t use much in the way of resources, and in some instances can help cure some of the incompatibilities your applications may have. Though I can’t find anything to support this, it would appear that the Application Compatibility Updates update the database of shims for the Application Experience service (they both seem to do the same thing, so hopefully they are working together). For a few more details, check out the MB’s Windows Security Blog, or this Microsoft KB article.