AES-256 is not illegal to use in the United States; domestic use of encryption technologies have generally never been restricted that way - there were, for some time, moves to allow for the possibility of communication intercepts  using warrants based on mandating the use of key escrow for non-military encryption, but that is an idea that died in practice.

The situation is somewhat more complex for companies which produce software which employs cryptographic techniques (which includes all kinds of other things than encryption, such as authentication, which is typically built out of very similar cryptographic building blocks) or which are involved in cross-border communications; for instance, for the United States there is the requirement for software companies to comply with the export control regulations set by the Bureau of Industry and Security (on top of the general need to be aware of the Office of Foreign Assets Control list of embargoed countries and individuals), and it's worth bearing in mind that virtually every country that you export *to* has similar kinds of regulation in place and that many of those countries may, unlike the United States, regulate their citizen's use of cryptographic software. As a result, one of the many jobs involved in releasing software which is sold in different countries is filing the necessary regulatory paperwork in the exporting and importing countries covering the way your product(s) uses cryptographic techniques. Even with the assistance of legal teams to deal with the detailed processes of filing, it's a tedious business auditing your software to ensure that the legal filings that result are complete and accurate.

This gets even more interesting when indirectly exporting something that aggregates products from other vendors, which often results from the internal operations of organizations that cross national boundaries: multinational customers of U.S. corporations therefore also tend to need to be aware of the impact of U.S. export control classification, which is why vendors such as Adobe and Symantec publish regulatory information about their products, such as at http://customercare.symantec.com/app/answers/detail/a_id/96 (do take a look at the PDF linked from there).

- Nigel