Magentoの対応バージョンは、過去幾度か変更されてきました。
リリースされた当初はPHP5.2系が主流だったので、PHP5.2系のみをサポートしていたのですが、その後時間の流れとともにPHPは5.3、5.4、5.5、5.6と順調にバージョンアップを続けています。

Magentoもこれに合わせて、サポートするPHPバージョンを少しずつ変えてきており、最新のバージョンではPHP5.4/5.5系を公式サポートバージョンとしています（Magento公式のシステム要件ページ）。
（実際には5.3でも動作はしますが、これから環境構築するのにPHP5.3を使うケースはほぼないと考えられます。）

PHPの言語としてのサポート期間

PHP公式サイトでは以下のように各バージョンのサポート期間が定められています。

バージョン リリース日 アクティブサポート期限 セキュリティサポート期限
5.3 2009/06/30 2013/07 2014/08/14
5.4 2012/03/01 2014/09/30 2015/09/30
5.5 2013/06/20 2015/06/20 2016/06/20
5.6 2014/08/28 2016/08/28 2017/08/28

このサポート期間によると、PHP5.4は2015年の秋にはサポート期間終了となり、PHP5.5も2016年の半ばにサポート期間終了となります。
もちろん、Linuxディストリビューションはそれぞれ独自に配布するPHPパッケージに対して、それぞれのサポート期限に合わせたメンテナンスを実施するとしているので、独自にPHPをソースからコンパイルして使用していない限りにおいては、慌てる必要はそこまで高くないと言って良いかと思います。 

MagentoがサポートするPHPバージョン

先程も触れましたが、Magento（あくまでここでは最新版のみとします）の対応PHPバージョンは5.4/5.5です。
5.4はもうすぐセキュリティメンテナンスが終了するため、これからサイトを構築するのであれば、PHP5.5を選ぶ必要があります。

過去のMagentoバージョンの場合はどうしたら良いのか

諸事情により、例えば過去のMagentoバージョンを用いて、PHP5.4/5.5の環境の上にサイトを構築しなければならない場合が時折あります。
そのような場合は、まず最初にMagentoが公式にリリースしているPHP5.4/5.5対応のためのパッチを適用してください。
弊社サイトでも過去記事で「MagentoをPHP5.4に対応させるパッチについて」を取り上げています。

PHP5.6は公式には現在非サポート

現状、最もメンテナンス期間が長く、安心して使い続けられるPHPのバージョンは5.6です。
これからサイトを構築する場合に、PHP5.6を使いたいという方は少なからずおられると思います。
ですが、MagentoはPHP5.6に現状対応していません。
PHP5.6で非推奨になった、iconv関連の関数がZend Frameworkの一部の処理で使用されているために、Zend Frameworkを利用しているMagentoにも影響を及ぼしています。

ですからMagentoをPHP5.6の上で動かそうとすると、おそらくエラーで動作しません。
6/23訂正：Magento CE 1.9.1.0以降（EE 1.14.1.0以降）はPHP5.6でも動作します。

どうしてもPHP5.6を使いたい場合は

プロジェクトの方針等の理由でPHP5.6を使用せざるをえない場合は、以下の方法で対処が可能です。 

  1. エラーの出るZend Frameworkの処理を見つける
  2. そのファイルをZend以下同じディレクトリ構成で、app/code/localにコピーする
  3. エラーの出る処理を修正する
  4. エラーが出なくなるまで繰り返す

上記の方法はあくまでも暫定的な対応です。
将来的にはMagento公式からPHP5.6対応のためのパッチもしくは対応がなされたバージョンがリリースされる模様です。
ただしこれはあくまでもMagento本体に限った話です。

エクステンションがPHP5.6で動作するかどうかはエクステンション開発者の裁量に委ねられているため、対応状況には差が出てきます。
いずれにせよMagentoで現状サイトを構築するのであれば、PHP5.5系までに留めておき、公式に対応が表明されたあとに移行を検討するのが無難であるといえるでしょう。