正規表現だけでも頑張ればできそうですが、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;
}