Do the U.S. export laws around AES-256 apply to applications hosted in the cloud?
To expand on Thomas's answer and my comment, in this particular case:
Exporting AES-256 encryption to certain customers is restricted by the US Government. For example, if you are selling to the government of China, you need an export license. But you can sell to a private entity in China.
You can not get a license to sell to certain embargoed countries and persons:
These include Cuba, Iran, Iraq, Libya, North Korea, Serbia, Sudan, Syria, and Taliban-controlled areas of Afghanistan.
Some countries, including China and Russia, require an import permit (or prohibit import) for encryption products.
Which doesn't give you a definitive answer where the cloud is ill-defined, so the solution will be to use a cloud provider who will agree under contract to limit the geographical distribution of your cloud. Many already do this - e.g. IronMountain allows you to choose the exact locations you want your data to be in, and cloud providers in the EU are supposed to keep customer data within the EU.
Laws of a given country apply wherever the country itself extends. It is a geographical context. It has been noted many times that space-based jurisdictions do not map well on a computerized, networked world, because it is often hard to know in which countries a given information transited between two systems (especially since "information" is not the same as "bunch of electrons whose wiggling in some copper cable somewhere is harnessed to transfer information"). The "cloud" just goes a bit further in that direction; it does not change things qualitatively, but quantitatively.
As an illustration of jurisdiction-related issues, consider the case of Sony against Geohot about the PS3 jailbreak, in particular this quote:
SCEA has sought to establish personal jurisdiction in California, because the US District Court there has a tendency to favor electronics companies in lawsuits thanks to some precedents set in prior landmark cases. The company maintains it has the grounds to file its suit in California, claiming that most of the people who downloaded the PS3 jailbreak can be traced to that particular state. That is to say that Hotz has the minimum contacts in Calfornia for Sony to bring its case before the state's District Court.
Sony got to much trouble to obtain log records from ISP to try to establish that jurisdiction thing. (Two weeks later, Sony and Geohot settled out of court, so we will never know how this would have turned out legally speaking.)
Yet you can be sure that some laws apply. There are places where no law from any specific country applies (high sea, outer space above 80km from Earth surface, maybe Antarctica) but even if the systems running the "cloud" were located on, say, an offshore platform, yourself and your computer would still physically reside in a more "mainstream" country, whose laws certainly apply.
At that point it becomes complex, because every country has its own set of laws and regulations on cryptographic systems and/or cryptographic keys. See this site for an extensive survey of crypto laws. At a minimum, consider the laws from the country you are, and those from the country where the cloud systems are located; if only because software you develop and upload to the could will go from the former to the latter.
Remember also that I am not entitled in any way to give legal advice. (I do not even really know whether such a disclaimer protects me or not.)