正規表現だけでも頑張ればできそうですが、phpだと、checkdate関数が使えますね。

http://www.devnetwork.net/viewtopic.php?f=29&t=13795

上記のスレッドでは、preg_matchでざっくりフォーマットの検査をして、checkdateで日付の妥当性を検査するのが主流のようです。

yyyy/MM/ddフォーマットならこんな感じですね。

if (preg_match('#^([0-9]{4})/([0-9]{2})/([0-9]{2})$#', $date, $part)) {
    return checkdate($part[2] , $part[3] , $part[1]);
} else {
    return false;
}