The term ASO ("app store optimization") is often used broadly as a catch-all to describe any effort that is undertaken to improve the download performance of an app via changes to its app store presence. Historically, these efforts were mostly oriented around app store search and thus resembled search engine optimization: keyword search estimates and the strategic use of those keywords in the various textual elements of the app's store profile page (title, description, and even package name).
But with the introduction of Google Play Analytics and, to a lesser extent (certainly a far lesser extent than was anticipated when the product was announced), iTunes Analytics, as well as products like Storemaven and Splitmetrics, developers now have the ability to actually optimize their store listings for conversion. The tests developers are now able to run -- such as icon and screenshot A/B testing -- are capable of substantively increasing the percentage of people that download an app after visiting its store page. This is true optimization, and from a marketing standpoint, it's fundamentally different than the keyword analysis that many people consider to be ASO.
What real app store optimization gives developers is an opportunity to widen their marketing funnel at the point of conversion. That is, it allows developers to improve the performance of their marketing assets at the moment that potential users are considering downloading an app. This is important because 1) there's already some intent inherent in viewing an app's store page (the person clicked on an ad for that app, searched for that app, etc.) and 2) it benefits every source of traffic driving potential users to that app store page. The second point bears elaboration: when store page conversion increases, then every single paid traffic channel becomes cheaper on a per-user, conversion basis (and even organic sources become more effective).
The value of real app store optimization is obvious when considered from this perspective: it increases the efficiency of paid campaigns and scales linearly with those budgets. If app store optimization (that is, the set of variant tests that improve the app store page view to download ratio) increases conversion by 10%, then a paid campaign delivers 10% more users at any level of budget, be it $100,000 or $1MM.
The same is not true of keyword analysis ("App Store SEO"). If a keyword analysis (and subsequent update to an app's description, keywords, package name, etc.) increases the number of installs in a weekly period by, say, 500, that increase is static: whether the developer is spending $100,000 or $1MM on paid traffic, the increase yielded by the keyword analysis won't change from 500 per week.
There is another aspect of keyword analysis that raises questions about its importance as a marketing strategy beyond being something that a developer simply does once immediately before launch: there is little support for the notion that arbitrary, keyword-driven app store search generates a meaningful amount of traffic to app store pages in the first place. There are broad, macro-level reasons and platform realities that explain why search would be more or less insignificant in terms of driving discovery, and then there's simply the fundamental difference in form factor and user behavior between web-based, text-oriented contextual search (from which app store SEO borrows its playbook) and the mobile app experience that makes search impractical for discovering new apps.
This isn't to say that smartphone owners don't search; according to a study performed by Nielsen, 63% of all app downloads are precipitated by an app store search. But a distinction needs to be drawn between a user searching for an app of which they are already aware and a person searching for an arbitrary keyword with a willingness to download whatever shows up first in the results. The first instance is search being used to locate an app and is certainly a common phenomenon (after all, how else can apps be located in a store?); the second is search being used to discover new apps and is of questionable practicality.
But ultimately, the values of both app store SEO and real app store optimization are defined by their abilities to drive installs. App store SEO taps into an existing volume of keyword searches and is constrained by that volume; no amount of keyword analysis can increase the number of times "puzzle game" or "ad blocker" or "flashlight app" are searched for each day. But real app store optimization -- the suite of tests that can be run on app store assets to increase conversion -- can increase installs proportionally with marketing spend, and the conjunction of these two activities widens both the mouth of the marketing funnel (awareness of the app) and its tail (conversion).
App store SEO can't do this: the number of people searching for a given term without a specific app already in mind is an exogenous factor that a developer can't influence. App store SEO is indisputably something that app developers should invest time into, but it's more of a best practice than a component of marketing strategy: since it relies on a volume of search that the developer can't influence and thus can't increase awareness of an app beyond that, app store SEO doesn't really fit, conceptually, within the marketing schema. And given the increasing number of tools available to developers to perform real app store optimization, it's appropriate that the distinction between app store SEO and app store optimization becomes more clear.